#include <iostream>
#include<fstream>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct nod{
    int info,c;
    nod *urm;
}*a[50001];

int n,nr,d[50001],viz[50001];

void add(int x,int poz,int cost){
    nod *q=new nod;
    q->info=x;
    q->c=cost;
    q->urm=a[poz];
    a[poz]=q;
}

void citire(){
    fin>>n>>nr;
    int x, poz, cost;
    for(int i=0;i<nr;i++){
        fin>>poz>>x>>cost;
        add(x,poz,cost);
    }

}

void dj(){
    for(int i=2;i<=n;i++)
        d[i]=50002;
    int ok=1;
    while(ok==1){
        ok=0;
        for(int i=1;i<=n;i++)
            if(d[i]!=50002&&viz[i]==0){
                ok=1;
                for(nod *p=a[i];p;p=p->urm)
                    if(d[p->info]>d[i]+p->c)
                        d[p->info]=d[i]+p->c;
                viz[i]=1;
                break;
            }
    }
}

void afis(){
    for(int i=2;i<=n;i++)
      if(d[i]==50002)
        fout<<0<<" ";
    else
        fout<<d[i]<<" ";
    fout<<"\n";
}

int main(){
    citire();
    dj();
    afis();
    return 0;
}