# include <fstream>
using namespace std;
long infinit=99999999;
int m,n,i,j,x[50000],viz[50000],start[50000],vmin,k,a,b,T[3][50000],cost,d[50000],poz,tata[50000];
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
void citire()
{
    cin >> n >> m;
    for(i=1;i<=n;i++)
    start[i]=0; k=0;
    for(i=1;i<=m;i++)
    {
        cin >> a >> b >> cost;
        k++;
        T[0][k]=b;
        T[1][k]=cost;
        T[2][k]=start[a];
        start[a]=k;

    }
}
void dijkstra(int vf)
{
    int viz[101],i,j,vmin;
    for(i=1;i<=n;i++)
    {
        viz[i]=0;
        tata[i]=-1;
        d[i]=infinit;
    }
    d[vf]=0;
    tata[vf]=0;
    for(i=1;i<=n;i++)
    {
        vmin=infinit;
        for(j=1;j<=n;j++)
        if(viz[j]==0 && d[j]<vmin)
        {
            vmin=d[j];
            poz=j;
        }
        if(vmin==infinit) break;
        viz[poz]=1;
        for(j=start[poz];j!=0;j=T[2][j])
        {
            if(viz[T[0][j]]==0 && d[poz]+T[1][j]<d[T[0][j]])
            {
                d[T[0][j]]=d[poz]+T[1][j];
                tata[T[0][j]]=poz;
            }
        }
    }
    /*
    for(i=1;i<=n;i++)
    {
        if(i!=vf && d[i]<infinit)
        {
            k=0; j=i;
            while(j!=0)
            {
                k++;
                x[k]=j;
                j=tata[j];
            }
            for(j=k;j>=1;j--)
            cout << x[j]<< " ";
            cout << endl;
        }
    } */
    for(i=2;i<=n;i++)
    {
    if(d[i]==infinit)
        cout << "0" << " ";
        else cout << d[i] << " ";
}
}
    int main()
    {
        citire();
        dijkstra(1);
        return 0;
    }