#include <iostream>
#include <fstream>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int inf=1<<30;
int n,m,a[10000][10000],v[10000],d[10000];
void init()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=inf;
}
void citire()
{
    int i,x,y,z;
    in>>n>>m;
    init();
    for(i=1;i<=m;i++)
    {
        in>>x>>y>>z;
        a[x][y]=z;
    }
}
void dijkstra()
{
    int i,min,ok=1,k;
    for(i=1;i<=n;i++)
        d[i]=a[1][i];
    d[1]=0;
    v[1]=1;
    while(ok)
    {
        min=inf;
        for(i=1;i<=n;i++)
            if(min>d[i] && v[i]==0)
            {
                min=d[i];
                k=i;
            }
        if(min!=inf)
        {
            v[k]=1;
            for(i=1;i<=n;i++)
                if(d[i]>d[k]+a[k][i])
                    d[i]=d[k]+a[k][i];
        }
        else
            ok=0;
    }

}
int main()
{
    citire();
    dijkstra();
    int i;
    for(i=2;i<=n;i++)
        if(d[i]==inf)
            out<<0<<" ";
        else
            out<<d[i]<<" ";
    return 0;
}