#include<stdio.h>
#include<fstream>
#include<utility>
#include<stdlib.h>
#include<vector>
#include<queue>
#define INF 2000000000
using namespace std;
typedef struct nod{ int x,d; nod *urm;}NODE;
NODE *v[50001];
typedef pair<int,int>PER;
int n,m,D[50001];

void citire()
{
    ifstream f("dijkstra.in");
    NODE *p;
    f>>n>>m;
    int x,y,d;
    for(int i=1;i<=m;++i)
    {
        f>>x>>y>>d;
        p=(NODE*)malloc(sizeof(NODE));
        p->x=y;
        p->d=d;
        p->urm=v[x];
        v[x]=p;
    }
}

void dijkstra()
{
    for(int i=0;i<=n;++i) D[i]=INF;
    D[1]=0;

    priority_queue<PER, vector<PER>, greater<PER> > Q;
    Q.push(make_pair(D[1],1));

    while(!Q.empty())
    {
        PER tmp = Q.top();
        Q.pop();
        int min=tmp.second;
        if(tmp.first!= D[min]) continue;
        NODE *q=v[min];

            while(q&&min)
            {
                if(D[min]+q->d < D[q->x])
                {
                    D[q->x]=D[min] + q->d;
                    Q.push(make_pair(D[q->x],q->x));
                }
                q=q->urm;
            }
    }

}

void scriere()
{
    FILE *f=fopen("dijkstra.out","w");
    for(int i=2;i<=n;++i)
        if(D[i]!=INF) fprintf(f,"%d ",D[i]);
        else fprintf(f,"0 ");
    fclose(f);
}

int main()
{
    citire();
    dijkstra();
    scriere();
    return 0;
}