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

using namespace std;

#define oo INT_MAX

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

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

void dijkstra(int st){
    int nod;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> PQ;
    for(int i=1;i<=n;i++){
        D[i]=oo;
    }
    PQ.push({0,st});
    D[st]=0;
    while(!PQ.empty()){
        nod=PQ.top().second;
        PQ.pop();
        U[nod]=1;
        for(auto vecin : L[nod]){
            D[vecin.first]=min(D[vecin.first],D[nod]+vecin.second);
            if(!U[vecin.first]){
                PQ.push({D[vecin.first], vecin.first});
            }
        }
    }
}

void read(){
    int x,y,t;
    in>>n>>m;
    for(int i=1;i<=m;i++){
        in>>x>>y>>t;
        L[x].push_back({y,t});
    }
}
int main(){
    read();
    dijkstra(1);
    for(int i=2;i<=n;i++){
        out<<D[i]<<" ";
    }
    return 0;
}