#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 5e4 + 5;
vector < pair <int, int> > g[NMAX]; // node first
int cost[NMAX];

class Compare{

public:
    bool operator()(pair <int, int> a, pair <int, int> b){
        return a > b;
    }
};

int main()
{
    int n, m, i, j;

    fin >> n >> m;

    for(i = 1; i <= m; ++i){
        int a, b, c;
        fin >> a >> b >> c;
        g[a].push_back({b, c});
    }

    for(i = 0; i < NMAX; ++i) cost[i] = INT_MAX;

    // first is the cost
    priority_queue < pair <int, int>, vector < pair <int, int> >, Compare > heap;
    heap.push({0, 1});

    while(!heap.empty()){
        int currentCost = heap.top().first;
        int currentNode = heap.top().second;
        heap.pop();

        if(cost[currentNode] != INT_MAX) continue;
        cost[currentNode] = currentCost;

        for(auto &it:g[currentNode]){
            if(cost[it.first] != INT_MAX) continue;
            heap.push({currentCost + it.second, it.first});
        }
    }

    for(i = 2; i <= n; ++i)
        if(cost[i] == INT_MAX) fout << 0 << ' ';
        else fout << cost[i] << ' ';

    return 0;
}