#include<bits/stdc++.h>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int DIM=50001;
const unsigned int oo=1<<30;

struct elem{
int cost;
int nod;
bool operator <(const elem &e)const {return cost>e.cost;}
};
int n,m;
int d[DIM];
bool viz[DIM];
priority_queue <elem> Q;
vector <elem> L[DIM];

void citire(){
    in>>n>>m;
    int i,x,y,c;
    elem w;
    for(i=1;i<=m;i++){
        in>>x>>y>>c;
        w.nod=y;w.cost=c;
   L[x].push_back(w);

    }in.close();}


    void rez(){
    int i,pozmin,k,c;
    elem w,w1;
    for(i=1;i<=n;i++)
    d[i]=oo;
d[1]=0;
w.cost=0;w.nod=1;
Q.push(w);
viz[1]=1;

while(!Q.empty()){
w=Q.top();
Q.pop();
pozmin=w.nod;
viz[pozmin]=1;

for(i=0;i<L[pozmin].size();i++)
{w1=L[pozmin][i];
k=w1.nod;
c=w1.cost;

if(!viz[k])
if(d[k]>d[pozmin]+c){
        d[k]=d[pozmin]+c;
        w1.cost=d[k];
        Q.push(w1);}
}}
}

void afisare(){
int i;
for(i=2;i<=n;i++)
    {if(d[i]==oo)d[i]=0;
    out<<d[i]<<" ";
    }
out<<endl;
out.close();
}


int main(){
citire();
rez();
afisare();
return 0;}