#include <iomanip>
#include <fstream>

using namespace std;

fstream fin("dijkstra.in", ios::in);
fstream fout("dijkstra.out", ios::out);

void dijkstra(int a[505][505], int n, int d[505]){
    int p[505],v[505],minim,i,j,pozmin;
    for (i=1;i<=500;i++){
        d[i]=2000; p[i]=0; v[i]=0;
    }
    d[1]=0;
    for (i=1;i<=n-1;i++){
        minim=2000; pozmin=2000;
        for (j=1;j<=n;j++){
            if ((minim>d[j])&&(v[j]==0)){
                minim=d[j];
                pozmin=j;
            }
        }
        if (minim==2000) break;
        v[pozmin] = 1;
        for (j=1;j<=n;j++){
            if ((v[j]==0)&&(d[pozmin]+a[pozmin][j]<d[j])){
                d[j] = d[pozmin]+a[pozmin][j];
                p[j] = pozmin;
            }
        }
    }
}

int main(){
    int n,m,i,j,x,y,z,a[505][505],d[505];
    fin>>n>>m;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++) a[i][j]=2000;

    for (i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        a[x][y]=z; 
    }
    
    dijkstra(a,n,d);
    
    for (i=2;i<=n;i++) fout<<d[i]<<" ";

    fin.close(); fout.close();
    return 0;
}