#include <bits/stdc++.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
typedef long long ll;

ll n, m;
ll sol[50005];
vector<pair<ll, ll> > graph[50005];
priority_queue<pair<ll, ll>, vector<pair<ll, ll> >, greater<pair<ll, ll> > > pq;
bitset<50005> check;

void dijkstra();

int main()
{

    fin >> n >> m;

    for(int i = 2; i <= n; ++i) sol[i] = LLONG_MAX;

    while(m--){
        int x, y, z;
        fin >> x >> y >> z;

        graph[x].push_back({z, y});
    }

    dijkstra();

    for(int i = 2; i <= n; ++i){
        fout << (sol[i] == LLONG_MAX ? 0 : sol[i]) << " ";
    }

    return 0;
}

void dijkstra(){
    pq.push({0, 1});

    while(!pq.empty()){
        pair<ll, ll> node = pq.top(); pq.pop();

        if(check[node.second]) continue;
        check[node.second] = true;

        for(auto it:graph[node.second]){
            pair<ll, ll> next = {node.first + it.first, it.second};

            if(next.first < sol[next.second]){
                sol[next.second] = next.first;
                pq.push(next);
            }
        }
    }
}