#include <bits/stdc++.h>
#define NMAX 50002

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector < pair < int, int > > v[NMAX];
vector < pair < int, int > > q; // un element => { x - nod, cost minim momentan din nodul 1 pana in nodul x }
bool visited[NMAX];
int n, m, d[NMAX];

void insert_element(pair < int, int > x)
{
    q.push_back(x);
}

// urmatorul element e de fapt elementul cu cel mai mic cost momentan
// returneaza indexul la care se afla elementul respectiv
int get_next_element()
{
    int minim = q[0].second;
    int min_index = 0;

    for (int i = 0; i < q.size(); ++ i) {
        if (q[i].second < minim) {
            minim = q[i].second;
            min_index = i;
        }
    }

    return min_index;
}

void delete_element(int index)
{
    q.erase(q.begin() + index);
}

bool is_structure_empty()
{
    return q.size() == 0;
}

void dijkstra() {
    d[1] = 0;
    insert_element({1, 0});

    while (!is_structure_empty()) {
        int curr_index = get_next_element();
        pair < int, int > curr = q[curr_index];
        //cout << curr.first << " " << curr.second << '\n';
        delete_element(curr_index);

        if (!visited[curr.first]) {
            visited[curr.first] = 1;

            for (auto it : v[curr.first]) {
                if (!visited[it.first] && d[it.first] > d[curr.first] + it.second) { // dp[i] = min(dp[tata] + 1, dp[i])
                    d[it.first] = d[curr.first] + it.second;
                    insert_element({it.first, d[it.first]});
                }
            }
        }
    }
}

int main()
{
    f >> n >> m;

    for (int i = 0; i < m; ++ i) {
        int x, y, cost;

        f >> x >> y >> cost;
        v[x].push_back({y, cost});
    }

    for (int i = 2; i <= n; ++ i) {
        d[i] = 2000000000;
    }

    dijkstra();

    for (int i = 2; i <= n; ++ i) {
        if (d[i] == 2000000000) {
            g << "0 ";
        } else {
            g << d[i] << " ";
        }
    }

    g << '\n';
    return 0;
}