#include <bits/stdc++.h>


using namespace std;
int n,m,d[100001];
vector<pair<int,int>>G[100001];
set<pair<int,int>>s;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int main(){
    fin>>n>>m;
    while(m--){
        int i,j,cost;
        fin>>i>>j>>cost;
        G[i].push_back({j,cost});
    }
    for(int i=2;i<=n;i++)
        d[i] = 1000000000;
    s.insert({0,1});
    while(!s.empty()){
        int nod = s.begin()->second;
        s.erase(*s.begin());
        for(auto x : G[nod]){
            int vec = x.first;
            int cost = x.second;
            if(d[vec]>d[nod]+cost){
                d[vec]=d[nod]+cost;
                s.insert({d[vec],vec});
            }
        }
    }
    for(int i=2;i<=n;i++)
        fout<<d[i]<<" ";
    return 0;
}