#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <limits>
#include <set>

using namespace std;

typedef pair<int,int> P;
const int INF = numeric_limits<int>::max()/2;

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

void read(int& n, int& m, vector<vector<P>>& a){
    fin>>n>>m;
    a.resize(n+1);
    int q,w,d;
    for(int i=1;i<=m;i++){
        fin>>q>>w>>d;
        a[q].push_back(P{w,d});
    }

}

void solve(int s, int& n, int& m, vector<vector<P>>& a, vector<int>& dist, set<P,greater<P>>& pq){
    dist[s]=0;
    pq.insert(P{0,s});
    while(!pq.empty()){
        P top=*pq.begin();
        pq.erase(pq.begin());
        //if(top.first!=dist[top.second]) continue;
        for(P e:a[top.second]){
            if(dist[e.first]>dist[top.second]+e.second){
                set<P,greater<P>>::iterator fd=pq.find(P{dist[e.first],e.first});
                if(fd!=pq.end()) pq.erase(fd);
                dist[e.first]=dist[top.second]+e.second;
                pq.insert(P{dist[e.first],e.first});
            }
        }
    }
}

void write(vector<int>& dist){
    for(int i=2;i<dist.size();i++){
        if(dist[i]==INF) fout<<0<<" ";
        else fout<<dist[i]<<" ";
    }
}

int main() {
    int n,m,st=1;

    vector<vector<P>> a;
    vector<int> dist;
   set<P,greater<P>> pq;

    read(n,m, a);
    dist.resize(n+1, INF);
    solve(st,n,m,a,dist,pq);
    write(dist);


    return 0;
}