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

typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<long long> vll;

#define INF 1e9+7

class Compare
{
public:
    bool operator() (pll a, pll b){
        return a.first > b.first;
    }
};

int main(void) {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    int n, m; cin >> n >> m;
    vector<pii> graph[250005];

    for (int i = 0; i < m; ++i) {
        int tmp; cin >> tmp;

        pii tmp_pair;
        cin >> tmp_pair.first;
        cin >> tmp_pair.second;

        graph[tmp].push_back(tmp_pair);
    }

    int source = 1;
    long long d[50005];
    for (int i = 0; i < 50005; ++i) d[i] = INF;

    bool visited[50005];
    memset(visited, 0, 50005);

    priority_queue<pll, std::vector<pll>, Compare> pq;
    
    pq.push({0, source});
    d[source] = 0;

    while (pq.size() != 0) {
        int src = pq.top().second;
        pq.pop();

        if (visited[src] == 1) continue;

        for (auto it : graph[src]) {
            if (d[it.first] > d[src] + it.second) {
                d[it.first] = d[src] + it.second;

                // if (visited[src] == 0) {
                    pq.push({d[it.first], it.first});
                //     visited[src] = 1;
                // }
            }
        }

        visited[src] = 1;
    }

    int cnt = 0;
    for (auto &it : d) {
        cnt++;
        if (cnt <= 2) continue;

        if (cnt > n + 1) break;
        if (it == INF) it = 0;
        cout << it << ' ';
        
    }

    return 0;
}