#include <bits/stdc++.h>

using namespace std;

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

struct str
{
    int cost;
    int nod;
};

constexpr int NMAX = 5e4 + 3, INF = 1e9;

int d[NMAX], n, m, a, b, c;
pair <int, int> aint[4 * NMAX];
bool sel[NMAX];

void update(int nod, int L, int R, int poz, int val)
{
    if(L == R){
        aint[nod].first = val;
        aint[nod].second = poz;
        return;
    }

    int mid = (L + R) >> 1;

    if(poz <= mid)
        update(2 * nod, L, mid, poz, val);
    else update(2 * nod + 1, mid + 1, R, poz, val);

    if(aint[2 * nod].first < aint[2 * nod + 1].first)
        aint[nod] = aint[2 * nod];
    else aint[nod] = aint[2 * nod + 1];
}

vector <str> G[NMAX];

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

    int dmin, poz;

    for(int i = 2; i <= n; i++) {
        update(1, 1, n, i, INF);
        d[i] = INF;
    }

    d[1] = 0;
    update(1, 1, n, 1, 0);
    for(int i = 1; i <= n; i++)
    {
        dmin = aint[1].first;
        poz = aint[1].second;

        sel[poz] = true;
        update(1, 1, n, poz, INF);
        for(auto it: G[poz]) {
            if(!sel[it.nod] && dmin + it.cost < d[it.nod]) {
                d[it.nod] = dmin + it.cost;
                update(1, 1, n, it.nod, dmin + it.cost);
            }
        }
    }

    for(int i = 2; i <= n; i++) {
        if(d[i] != INF)
            fout << d[i] << " ";
        else fout << "0 ";
    }
    fout << '\n';
    return 0;
}