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

using namespace std;
FILE *f,*g;

struct bla
{
    int a,b;
};
struct compar
{
    bool operator() (bla X, bla Y)
    {
        return (X.b> Y.b);
    }
};

priority_queue <bla, vector < bla >,compar> q;
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.push({1,0});
    for(int i=1;i<=2;++i)
    {
        int val=q.top().a;
    }
    while(!q.empty())
    {
        no=q.top().a;
        q.pop();
            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.push({vecin,dist});
                }
            }
    }
    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;
}