#include<bits/stdc++.h>
using namespace std;
const int DIM=50001;
const int oo=1000000000;

struct elem{
int cost;
int nod;
bool operator <(const elem &x)const {return cost>x.cost;}
};

int n,m,d[DIM];
vector <elem> L[DIM];

void citire(){
    ifstream in("dijkstra.in");
    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();}


   inline void rez(){
       priority_queue <elem> Q;
    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);

while(!Q.empty()){
w=Q.top();
Q.pop();
pozmin=w.nod;

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

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

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


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