#include <bits/stdc++.h>
#define INF 1000000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,s,x,y,c,a[101][101],d[101],m,viz[101],i,k,max1;
vector <int >v[101];

int main()
{
f>>n>>m;
s=1;
for(i=1;i<=m;i++)
{
    f>>x>>y>>c;
   v[x].push_back(y);
   a[x][y]=c;

}
for(i =1 ; i <= n ; i ++ )
    if(a[s][i])
    d[i] = a[s][i];
else
    d[i]=INF;

 viz[s]=1;d[s]=0;
 d[0]=INF;

 for(k=1;k<n;k++)
 {
     max1=0;
     for(i=1;i<=n;i++)
     if(!viz[i]&&d[i]<d[max1])
     max1=i;
if(max1)
{
    viz[max1]=1;
    for(i=0;i<v[max1].size();i++)
    {
        x=v[max1][i];
        if(viz[x]==0&&d[x]>d[max1]+a[max1][x])
            d[x]=d[max1]+a[max1][x];
    }
}

 }

 for(i=2;i<=n;i++)
    if(d[i]==INF)
    g<<0<<" ";
    else
        g<<d[i]<<" ";

    return 0;
}