#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
struct Edge
{ int i, j, w;
};

Edge a[100001];
int n, m, d[100001], start, endd, pred[100001];
void in()
{ scanf("%d %d %d %d", &n, &m, &start, &endd);
  for (int i = 0; i < m; i++)
  { scanf("%d %d %d", &a[i].i, &a[i].j, &a[i].w);
    a[i].i--;
    a[i].j--;
  }
    
}

void FordBellman(int s1)
{ memset(pred, -1, sizeof(pred));
  for (int i = 0; i < n; i++)
    d[i] = 1000000001;
  
  d[s1] = 0;
  
  for (int i = 0; i < n - 1; i++)
    for (int j = 0; j < m; j++)
      if (d[a[j].j] > d[a[j].i] + a[j].w)
      { d[a[j].j] = d[a[j].i] + a[j].w;
        pred[a[j].j] = a[j].i;
      }
  
  for (int i = 0; i < m; i++)
    if (d[a[i].j] > d[a[i].i] + a[i].w)
    { printf("Error! There is a negative cycle in the graph.\n");
      exit(1);
    }
}

void printPath(int i)
{ if (pred[i] == -1)
    return;
  
  printPath(pred[i]);
  printf(" %d", i + 1);
}

void print()
{ for (int i = 0; i < n; i++)
    printf("Cost of shortest path from %d to %d: %d\n", start, i + 1, d[i]);
  
  printf("Shortest path from %d to %d: %d", start, endd, start);
  printPath(endd - 1);
  printf(", with cost %d\n", d[endd - 1]);
}

int main()
{ 
  in();
  FordBellman(start - 1);
  print();
  
  return 0;
}
/*
6 9 1 6
1 3 20
1 2 10
2 4 50
2 5 10
3 5 33
3 4 20
4 5 -20
4 6 -2
5 6 1
*/