#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("dijkstra.in");ofstream fout("dijkstra.out");
int i,n,p,S[50001],D[50001],T[50001],A[10001][10001],x,y,c,q=10000001,mini,j,nod,k,m;
int main()
{
    fin>>n>>m;p=1;
    for(i=1;i<=m;i++)
    {fin>>x>>y>>c;A[x][y]=c;}
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++) {if(A[i][j]==0) A[i][j]=q;if(i==j) A[i][j]=0;}

    for(i=1;i<=n;i++) D[i]=A[p][i];
    S[p]=1;
    for(i=1;i<=n;i++) if(D[i]<q&&D[i]&&S[i]) T[i]=p;
    for(i=1;i<=n;i++)
    {
        mini=q;
        for(j=1;j<=n;j++)
            if(!S[j])
                if(D[j]<mini)
                {
                    mini=D[j];
                    nod=j;
                }
            S[nod]=1;
        for(j=1;j<=n;j++)
            if(!S[j])
                if(mini+A[nod][j]<D[j])
                {
                    D[j]=mini+A[nod][j];
                    T[j]=nod;
                }
    }
    for(i=2;i<=n;i++)
    {
        if(D[i]!=q) fout<<D[i]<<' ';
        else fout<<-1<<' ';
    }
    return 0;
}