/*可解决图中存在环（负权值）问题，dijksta则不能
O(V*E)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int max_v=1170;
const int max_e=2170;
const int INF=0x7fffffff;
struct edge
{
int from,to,cost;
}es[max_e];//边
int d[max_v];//最短距离
int v,e;//v顶点
//从顶点s出发到所有点最短距离
void short_distance(int Begin)
{
for(int i=1;i<=v;i++)
{
d[i]=INF;
}
d[Begin]=0;
while(true)
{
bool update=false;
for(int j=0;j<e;j++)
{
edge E=es[j];
if(d[E.from]!=INF&&d[E.to]>d[E.from]+E.cost)
{
d[E.to]=d[E.from]+E.cost;
update=true;
}
}
if(!update)
break;
}
}
int main()
{
cin>>v>>e;
for(int i=0;i<e;i++)
{
cin>>es[i].from>>es[i].to>>es[i].cost;
}
int Begin,End;
cin>>Begin>>End;
short_distance(Begin);
for(int i=1;i<=v;i++)
cout<<d[i]<<' ';
cout<<endl;
cout<<d[End]<<endl;
return 0;
}