//DIJKSTRA - PRIORITY QUEUE
#include <iostream>
#include <fstream>
#include <cstdio>
#include <queue>
#include <vector>
#define N 50000
#define INF (1<<30)
using namespace std;
//ifstream in("dijkstra.in");
//ofstream out("dijkstra.out");
FILE * in=fopen("dijkstra.in","r");
FILE * out=fopen("dijkstra.out","w");

int n,m;

struct nod{
    int vecin;
    int cost;
    struct nod *urm;
}*L[N+5],*act;

int d[N+2]; //distanta de la nodul radacina(1) la toate celelalte
bool viz[N+2]; //vector noduri vizitate
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; //coada de prioritati

int main()
{
//citiri
    /*int x,y,c;
    in>>n>>m;
    for(int i=1;i<=m;++i)
    {
        in>>x>>y>>c;
        act=new nod;
        act->vecin=y;
        act->cost=c;
        act->urm=L[x];
        L[x]=act;
    }*/
    int x,y,c;
    fscanf(in,"%d %d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        fscanf(in,"%d %d %d",&x,&y,&c);
        act=new nod;
        act->vecin=y;
        act->cost=c;
        act->urm=L[x];
        L[x]=act;
    }

//algoritmul dijkstra
    //initializeaza distantele cu +INF, iar radacina cu 0
    for(int i=1;i<=n;++i)
        d[i]=INF;
    d[1]=0;
    //adauga radacina in coada
    pq.push(make_pair(d[1],1));
    //incepe parcurgerea
    while(!pq.empty())
    {
        //extrage nodul nevizitat la distanta cea mai mica
        int nodMin = pq.top().second;
        viz[nodMin]=1;
        pq.pop();
        //exploreaza vecinii nodului extras, actualizand distantele
        for(struct nod *p=L[nodMin]; p!=NULL; p=p->urm)
        {
            int vecin = p->vecin;
            int dist = p->cost;
            if(viz[vecin]==0 && d[vecin]>d[nodMin]+dist && dist!=INF && d[nodMin]!=INF)
            {
                d[vecin]=d[nodMin]+dist;
                pq.push(make_pair(d[vecin],vecin));
            }
        }
    }

//afiseaza distantele finale
    for(int i=2;i<=n;++i)
    {
        /*if(d[i]==INF) out<<"0 ";
        else out<<d[i]<<" ";*/
        if(d[i]==INF)
            fprintf(out,"0 ");
        else
            fprintf(out,"%d ",d[i]);
    }

    return 0;
}