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

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int nmax = 5005;
int extractMin(unordered_set<int> s, int* dMin, int N){
    int mini = INT_MAX;
    int poz = - 1;
    for(int i = 1; i <= N; ++i)
        if(s.find(i) == s.end() && dMin[i] < mini){
            mini = dMin[i];
            poz = i;
        }
    return poz;
}

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));

    while(!(pq.empty())){
        int crt = extractMin(pq);
        for(auto vecin: adj[crt]){
            int nnod = vecin.first;
            int ccost = vecin.second;
            if(ccost + dMin[crt] < dMin[nnod])
                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;
}