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

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int nmax = 50005;

int extractMin(priority_queue<pair<int, int>>& pq){
    int temp = pq.top().second;
    pq.pop();
    return temp;
}
int main()
{   int N, M;
    vector <pair<int, int>> adj[nmax];
    priority_queue<pair<int, int>> pq;  /// tine perechi de tip (cost, nod)

    int dMin[nmax];
    fin >> N >> M;
    for(int k = 0; k < M; ++k){
        int i, j, cost;
        fin >> i >> j >> cost;
        adj[i].push_back(make_pair(j, cost));
    }

    dMin[1] = 0;
    for(int i = 2; i <= N; ++i)
        dMin[i] = INT_MAX / 2;
    pq.push(make_pair(0, 1));
    bool inCoada[nmax] = {false};

    while(!(pq.empty())){
        int crt = extractMin(pq);
        inCoada[crt] = true;
        for(auto vecin: adj[crt]){
            int nnod = vecin.first;
            int ccost = vecin.second;
            if(ccost + dMin[crt] < dMin[nnod] && inCoada[nnod] == false)
                {
                    dMin[nnod] = ccost + dMin[crt];
                    pq.push(make_pair(dMin[nnod], nnod));
                }
        }
    }
    for(int i = 2; i <= N; ++i)
        if(dMin[i] != INT_MAX / 2)
            fout << dMin[i] << ' ';
        else fout << 0 << ' ';

	return 0;
}