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

using namespace std;

const int inf=1<<25;

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 dijkstra(int st){
    int nod;
    D[st]=0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> PQ;
    PQ.push({0,st});
    while(!PQ.empty()){
        nod=PQ.top().second;
        PQ.pop();
        if(!U[nod]){
            U[nod]=1;
            for(auto x : L[nod]){
                if(D[x.first]>D[nod]+x.second){
                    D[x.first]=D[nod]+x.second;
                    if(!U[x.first]){
                        PQ.push({D[x.first],x.first});
                    }
                }
            }
        }
    }
}
void solve(){
    for(int i=1;i<=n;i++)
        D[i]=inf;
    dijkstra(1);
    for(int i=2;i<=n;i++){
        if(D[i]==inf)
            out<<"0 ";
        else out<<D[i]<<" ";
    }
}
int main(){
    read();
    solve();
    return 0;
}