#include<cstdio>
#include<fstream>
#include<vector>
#define M 1<<30
using namespace std;
FILE* f=fopen("dijkstra.in","r");
FILE* g=fopen("dijkstra.out","w");
struct nod{
    int inf;
    int c;
};
vector<nod>v[50001];
int m,n,cost[50001],viz[50001];
void citire()
{
    nod a;
    int x,y,z;
    fscanf(f,"%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&x,&y,&z);

        a.inf=y;
        a.c=z;
        v[x].push_back(a);
    }
}
int co(int j,int nodul)
    {
        int i;
        for(i=0;i<=v[j].size();i++)
            if(v[j][i].inf==nodul)
                return v[j][i].c;
        return M;
    }
void dijkstra(int nodul)
{
    int i,j,coo,maxi,k,nodcur;
    for(i=1;i<=n;i++)
        cost[i]=M;
    cost[nodul]=0;
    for(i=0;i<v[nodul].size();i++)
        cost[v[nodul][i].inf]=v[nodul][i].c;
    viz[nodul]=1;
    for(i=1;i<=n-1;i++)
       {
           maxi=M;
           for(j=1;j<=n;j++)
                if(cost[j]<maxi&&!viz[j])
                    maxi=cost[j],nodcur=j;
           viz[nodcur]=1;
            for(k=0;k<v[nodcur].size();k++)
                if(cost[v[nodcur][k].inf]>cost[nodcur]+v[nodcur][k].c)
                    cost[v[nodcur][k].inf]=cost[nodcur]+v[nodcur][k].c;

       }

    for(i=2;i<=n;i++)
        if(cost[i]==M)
           fprintf(g,"0 ");
        else fprintf(g,"%d ",cost[i]);
}
int main()
{
    citire();
    dijkstra(1);
    return 0;
}