#include <fstream>
#define inf 1<<30
#define N 20010
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,i,j,D[N],T[N],S[N],a[N][N],x,y,cost;
void read(){
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        a[x][y]=cost;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(a[i][j]==0 && i!=j)
                a[i][j]=inf;
}
void intit(){
    for(i=2;i<=n;i++)
    {
        D[i]=a[1][i];
        if(D[i]<inf)
            T[i]=1;
    }
    S[1]=1;
}
int poz_min(){
    int m=inf,i,poz;
    for(i=2;i<=n;i++)
        if(S[i]==0)
            if(D[i]<m)
            {
                m=D[i];
                poz=i;
            }
    return poz;
}
void Dijkstra(){
    int i,poz;
    poz=poz_min();
    S[poz]=1;
    for(i=1;i<=n;i++)
    {
        if(D[i]>D[poz]+a[poz][i])
        {
            D[i]=D[poz]+a[poz][i];
            T[i]=poz;
        }
    }
}
void write(){
    int i;
    for(i=2;i<=n;i++)
        fout<<D[i]<<" ";
}
int main(){
    read();
    intit();
    for(i=1;i<n;i++)
        Dijkstra();
    write();
    fin.close();
    fout.close();
    return 0;
}