#include <bits/stdc++.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
using namespace std;

int n, m, idx[250001], dis[250001];
bool inCoada[250001]={false};
vector<pair<int, int>>v[250001];
priority_queue< pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> >pq;
const int INF=1e9;

int main(){

    int i, e, s, nr, cont=0, a, b, c, am, bm, vec;
    f >> n >> m;
    for(i=1; i<=m; ++i)
    {
        f >> a >> b >> c;
        v[a].push_back({b, c});
    }
    dis[1]=0;
    for(i=2; i<=n; ++i)
        dis[i]=INF;

    pq.push({0, 1});

    while(!pq.empty()){
        am=pq.top().first;
        bm=pq.top().second;
        pq.pop();

        if(am>dis[bm])continue;

        for(const auto vecin:v[bm]){
            vec=vecin.first;
            if(vecin.second+dis[bm] < dis[vecin.first]){
                dis[vecin.first]=vecin.second+dis[bm];
                pq.push({vecin.second+dis[bm], vecin.first});
            }

        }

    }

    for(i=2; i<=n; ++i)
        if(dis[i]!=INF)g << dis[i] << " ";


    return 0;
}