#include <iostream>
#include <stack>
#define MAX 100
#define VOCUC 1000
int LuuVet[MAX];
int ChuaXet[MAX];
int DoDaiDuongDiToi[MAX];
int SAU_NUT[MAX][MAX];
int L[MAX][MAX];
struct DOTHI {
int n;
int a[MAX][MAX];
};
void DStoMTK(DOTHI &g) {
int m;
std::cin >> g.n >> m;
for (int i = 1; i <= g.n; i++) {
for (int j = 1; j <= g.n; j++) {
g.a[i][j] = 0;
}
}
int u, v, w;
for (int i = 1; i <= m; i++) {
std::cin >> u >> v >> w;
g.a[u][v] = w;
}
}
int TimDuongDiNhoNhat(DOTHI g) {
int li = -1;
float p = VOCUC;
for (int i = 1; i <= g.n; i++) {
if (ChuaXet[i] == 0 && DoDaiDuongDiToi[i] < p) {
p = DoDaiDuongDiToi[i];
li = i;
}
}
return li;
}
void CapNhatDuongDi(int u, DOTHI g) {
ChuaXet[u] = 1;
for (int v = 1; v <= g.n; v++) {
if (ChuaXet[v] == 0 && g.a[u][v] > 0 && g.a[u][v] < VOCUC)
if (DoDaiDuongDiToi[v] > DoDaiDuongDiToi[u] + g.a[u][v]) {
DoDaiDuongDiToi[v] = DoDaiDuongDiToi[u] + g.a[u][v];
LuuVet[v] = u;
}
}
}
void Dijkstra(int S, int F, DOTHI g) {
std::stack<int> temp;
for (int i = 1; i <= g.n; i++) {
ChuaXet[i] = 0;
DoDaiDuongDiToi[i] = VOCUC;
LuuVet[i] = -1;
}
DoDaiDuongDiToi[S] = 0;
while (ChuaXet[F] == 0) {
int u = TimDuongDiNhoNhat(g);
if (u == -1) break;
CapNhatDuongDi(u, g);
}
if (ChuaXet[F] == 1) {
temp.push(F);
int i = LuuVet[F];
while (i != -1) {
temp.push(i);
i = LuuVet[i];
}
std::cout << DoDaiDuongDiToi[F] << std::endl;
while (!temp.empty()) {
std::cout << temp.top() << " ";
temp.pop();
}
} else
std::cout << "-1";
}
void Floyd(DOTHI g) {
std::stack<int> temp;
for (int i = 1; i <= g.n; i++) {
for (int j = 1; j <= g.n; j++) {
if (g.a[i][j] > 0) {
SAU_NUT[i][j] = j;
L[i][j] = g.a[i][j];
} else {
SAU_NUT[i][j] = -1;
L[i][j] = VOCUC;
}
}
}
for (int k = 1; k <= g.n; k++) {
for (int i = 1; i <= g.n; i++) {
for (int j = 1; j <= g.n; j++) {
if (L[i][j] > L[i][k] + L[k][j]) {
L[i][j] = L[i][k] + L[k][j];
SAU_NUT[i][j] = SAU_NUT[i][k];
}
}
}
}
int startVertex, targetVertex;
std::cin >> startVertex >> targetVertex;
if (SAU_NUT[startVertex][targetVertex] == -1) {
std::cout << "-1";
} else {
std::cout << L[startVertex][targetVertex] << std::endl;
std::cout << startVertex << " ";
int u = startVertex;
while (SAU_NUT[u][targetVertex] != targetVertex) {
u = SAU_NUT[u][targetVertex];
std::cout << u << " ";
}
std::cout << targetVertex << " ";
}
}
int main() {
DOTHI g;
DStoMTK(g);
//int startVertex, targetVertex;
//std::cin >> startVertex >> targetVertex;
// Dijkstra(startVertex, targetVertex, g);
Floyd(g);
return 0;
}