#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

int D[50005];
int U[50005];
vector<pair<int,int>> L[50005];
int n,m,p;

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

void read(){
    int x,y,d;
    in>>n>>m;
    p=1;
    for(int i=1;i<=m;i++){
        in>>x>>y>>d;
        L[x].push_back({y,d});
    }
}
void solve(){
    int imin;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> PQ;
    for(int i=1;i<=n;i++){
        if(i!=p)D[i]=1000000;
    }
    PQ.push({0,p});
    while(!PQ.empty()){
        imin=PQ.top().second;
        PQ.pop();
        if(!U[imin]){
            U[imin]=1;
            for(auto it=L[imin].begin();it!=L[imin].end();it++){
                D[(*it).first]=min(D[(*it).first], D[imin] + (*it).second);
                if(!U[(*it).first]) //! <- less time
                    PQ.push({D[(*it).first], (*it).first});
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(D[i]==1000000)out<<0;
        else out<<D[i];
        out<<" ";
    }
}
int main(){
    read();
    solve();
    return 0;
}