#include <bits/stdc++.h>
#define nmax 50005
#define inf (int)(1e9)
#define intpair pair <int,int>
#define Vecin1 Edge.first
#define Vecin2 Edge.second

using namespace std;

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

int N,M;

vector <intpair> ADC[nmax];

inline void ADDE(int x,int y,int w){
    ADC[x].push_back({y,w});
}

int Dist[nmax];

priority_queue <intpair,vector <intpair>,greater <intpair>> PQ;

void dijk(){
    for(int i=1;i<=N;i++)
        Dist[i]=inf;
    Dist[1]=0;
    PQ.push({0,1});
    intpair Top;
    while(!PQ.empty()){
        Top=PQ.top();
        PQ.pop();
        if(Top.first !=Dist[Top.second])continue;
        for(auto Edge:ADC[Top.second])
            if(Dist[Vecin1]>Dist[Top.second]+Vecin2)
                Dist[Vecin1]=Dist[Top.second]+Vecin2,
                   PQ.push({Dist[Vecin1],Vecin1});
    }
}

void citire(){
    fin>>N>>M;
    for(int i=1,x,y,z;i<=M;i++)
        fin>>x>>y>>z,ADDE(x,y,z);

}

void rezolvare(){
    citire();
    dijk();
    for(int i=2;i<=N;i++)
        if(Dist[i]==inf)fout<<"0"<<" ";
    else fout<<Dist[i]<<" ";
}

int main()
{
    rezolvare();
    return 0;
}