#include <bitset>
#include <stdio.h>
#include <vector>
#include <set>

using namespace std;
FILE *f,*g;

struct bla
{
    int a,b;
};
struct compar
{
    bool operator() (bla X, bla Y)
    {
        return (X.b< Y.b);
    }
};
set <bla,compar> q;
set <bla> :: iterator it;


vector < bla > nod[50002];
bool viz[50002];
int drum[50002];

int main()
{
    int m,n,i,j,x,y,c,no,dist,cost,vecin;
    f=fopen("dijkstra.in","r");
    g=fopen("dijkstra.out","w");
    fscanf(f,"%d %d",&n,&m);
    for(i=1;i<=m;++i)
    {
        fscanf(f,"%d %d %d",&x,&y,&c);
        nod[x].push_back({y,c});
    }
    for(i=2;i<=n;++i)
        drum[i]=2000000000;
    q.insert({1,0});
    while(!q.empty())
    {
        it=q.begin();
        no=(*it).a;
        q.erase(it);
        if(!viz[no])
        {
            for(i=0;i<nod[no].size();++i)
            {
                vecin=nod[no][i].a;
                cost=nod[no][i].b;
                dist=drum[no]+cost;
                if(dist<drum[vecin])
                {
                    drum[vecin]=dist;
                    q.insert({vecin,dist});
                }
            }
        }
        viz[no]=1;
    }
    for(i=2;i<=n;++i)
    {
        if(drum[i]==2000000000)
            fprintf(g,"0 ");
        else
            fprintf(g,"%d ",drum[i]);
    }
    fclose(f);
    fclose(g);
    return 0;
}