#include <stdio.h>
#include <stdlib.h>
#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(struct DOTHI* g)
{
int m;
scanf("%d %d", &(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++)
{
scanf("%d %d %d", &u, &v, &w);
g->a[u][v] = w;
}
}
int TimDuongDiNhoNhat(struct 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, struct 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, struct DOTHI g)
{
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)
{
printf("%d\n", DoDaiDuongDiToi[F]);
int i = LuuVet[F];
while (i != -1)
{
printf("%d ", i);
i = LuuVet[i];
}
}else printf("-1");
}
void Floyd(struct DOTHI g)
{
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;
scanf("%d %d", &startVertex, &targetVertex);
if (SAU_NUT[startVertex][targetVertex] == -1)
{
printf("-1");
}
else
{
printf("%d\n", L[startVertex][targetVertex]);
printf("%d ", startVertex);
int u = startVertex;
while (SAU_NUT[u][targetVertex] != targetVertex)
{
u = SAU_NUT[u][targetVertex];
printf("%d ", u);
}
printf("%d ", targetVertex);
}
}
int main() {
struct DOTHI g;
DStoMTK(&g);
Floyd(g);
return 0;
}