#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<time.h>
using namespace std; int map[100][100]={0};
int book[100]={0};
int dis[100]={0};//顶点
int n=0,m=0;
int minn=99999;
int u=0; void Dijk()
{
for(int i=1;i<=n;i++)
{
minn=99999;
for(int j=1;j<=n;j++)
{
if(!book[j] && dis[j]<minn)
{
minn=dis[j];
u=j;
}
}//找到最小的u book[u]=1;
for(int j=1;j<=n;j++)//松弛j点
{
if(dis[u]+map[u][j]<dis[j])
{
dis[j]=dis[u]+map[u][j];//修改
}
}
//book[i]=1;
}
} int main()
{
//freopen("Dijkstra_out.txt","r",stdin);
cin>>n>>m; int a=0,b=0; for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j)
{
map[i][j]=0;
}
else
{
map[i][j]=999999;
}
}
}//初始化 for(int i=1;i<=m;i++)
{
cin>>a>>b;
cin>>map[a][b];//读入边
} //初始化 for(int i=1;i<=n;i++)
{
dis[i]=map[1][i];
}//读入dis数组 // for(int i=1;i<=n;i++)
// {
// cout<<dis[i]<<" ";
// }
// Dijk(); for(int i=1;i<=n;i++)
{
cout<<dis[i]<<" ";
} // for(int i=1;i<=n;i++)
// {
// //for(int j=1;j<=n;j++)
// // {
// cout<<map[1][i]<<" ";
// // }
// //cout<<"\n";
// }//输出
//cout<<map[1][5]<<endl; cout<<(double)clock()/CLOCKS_PER_SEC; return 0;
}