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

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

int n, m, p;
int dist[50005];
bool viz[50005];
priority_queue <pair<int, int>> pq;
vector<pair<int, int>>v[50005];

void djikstra()
{
    while(!pq.empty()){
        int nod = pq.top().second;
        pq.pop();
        if(!viz[nod]){
            for(auto i : v[nod]){
                if(dist[i.first]>dist[nod]+i.second){
                    dist[i.first] = dist[nod]+i.second;
                    pq.push(make_pair(-dist[i.first], i.first));
                }
            }
            viz[nod] = true;
        }
    }
}

int main(){
    /*ios_base::sync_with_stdio(false);
    cin.tie(nullptr);*/
    fin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int x, y, c;
        fin >> x >> y >> c;
        v[x].push_back(make_pair(y, c));
    }
    for(int i = 1; i <= n; ++i){
        dist[i] = 2e9;
    }
    dist[1] = 0;
    pq.push(make_pair(0, 1));
    djikstra();
    for(int i = 2; i <= n; ++i){
        if(dist[i]==2e9)
            fout << 0 << " ";
        else
            fout << dist[i] << " ";
    }
    return 0;
}