#include <fstream>
#include <vector>
#define oo 100000
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n,m,w[10001][10001],distanta[10001],vecin[10001],viz[10001];

//fa - functie auxiliara
//n,m cu semnificatia din enunt, w matricea de adiacenta
//d vectorul de distante, vecin vectorul de vecini ce poate fi folosit si pentru afisarea drumului
//viz vectorul nodurilor vizitate

void citeste_fa()
{
    int i,j,x,y,k;
    f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j) w[i][j]=oo;
            else w[i][j]=0;
    for(i=1;i<=m;i++)
        f>>x>>y>>k,w[x][y]=k;
}

void aplica_dijkstra_fa(int s)
{
    int i,j,k,minv;
    for(i=1;i<=n;i++){
        distanta[i]=w[s][i];
        if(i!=s&&distanta[i]!=oo) vecin[i]=s;
    }
    viz[s]=1;
    for(k=1;k<n;k++){
        minv=oo;
        for(i=1;i<=n;i++)
            if(viz[i]==0&&distanta[i]<minv) minv=distanta[i],j=i;
        for(i=1;i<=n;i++)
            if(viz[i]==0)
                if(distanta[i]>distanta[j]+w[j][i])
                    distanta[i]=distanta[j]+w[j][i],vecin[i]=j;
        viz[j]=1;
    }
}

int main()
{
    citeste_fa();
    aplica_dijkstra_fa(1);
    for(int i=2;i<=n;i++) g<<distanta[i]<<' ';
    g<<'\n';
    return 0;
}