#include <bits/stdc++.h>
using namespace std;

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

vector<vector<pair<int,int>>> g;
int n,m;

void disjkstra(int x){
    priority_queue<pair<int,int>> pq;
    pq.push({x,0});
    vector<int> p(n+1,INT_MAX-1);
    p[1]=0;
    while(pq.size()){
        int curr=pq.top().first;
        pq.pop();
        for(auto it:g[curr]){
            p[it.first]=min(p[curr]+it.second,p[it.first]);
            it.second*=-1;
            pq.push(it);
            it.second*=-1;
        }
    }
    for(int i=2;i<p.size();++i){
        fout<<(p[i]==INT_MAX?0:p[i])<<" ";
    }
}

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