#include <bits/stdc++.h>
#define inf 1000000001
#define nmax 50001

using namespace std;

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

int n;
int m;
vector<pair<int,int>> ADJ[nmax];
int D[nmax];
int VIZ[nmax];
priority_queue<pair<int,int>> Q;

int main()
{
    fin >> n >> m;
    for(int i=1;i<=m;i++){
        int a,b,c;
        fin >> a >> b >> c;
        ADJ[a].push_back({b,c});
    }

    for(int i=1;i<=n;i++) D[i]=inf;
    D[1]=0;
    Q.push({0,1});
    while(!Q.empty()){
        int a=Q.top().second; Q.pop();
        if(VIZ[a]==1) continue;
        VIZ[a]=1;
        for(auto i:ADJ[a]){
            int b=i.first, w=i.second;
            if(D[a]+w<D[b]){
                D[b]=D[a]+w;
                Q.push({-D[b],b});
            }
        }
    }
    for(int i=2;i<=n;i++)
        if(D[i]==inf)
            fout << 0 << ' ';
        else
            fout << D[i] << ' ';
    return 0;
}