#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n, m, a[1001][1001], pred[1001][1001], start, endd;
void in()
{ scanf("%d %d %d %d", &n, &m, &start, &endd);
  
  memset(pred, -1, sizeof(pred));
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      a[i][j] = 1000000001;
  
  for (int i = 0; i < m; i++)
  { int v1, v2, weight;
    scanf("%d %d %d", &v1, &v2, &weight);
    a[v1 - 1][v2 - 1] = weight;
    pred[v1 - 1][v2 - 1] = v1 - 1;
  }
}

void Floyd()
{ for (int i = 0; i < n; i++)
    a[i][i] = 0;
  
  for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (a[i][j] > a[i][k] + a[k][j])
        { a[i][j] = a[i][k] + a[k][j];
          pred[i][j] = k;
        }
  
  for (int i = 0; i < n; i++)
    if (a[i][i] < 0)
    { printf("Cycle with negative length.\n");
      exit(1);
    }
}

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

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

int main()
{ 
  in();
  Floyd();
  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
*/