#include <bits/stdc++.h>
#define INF 1e9
#define NMAX 50004

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

int n, m, start, x0 = 1;
int dp[NMAX], uz[NMAX];
vector < pair <int, int> > G[NMAX];
int H[NMAX]; /// retin varfurile organizate ca un heap
int nr;
int poz[NMAX];
///poz[x] = 0 daca x nu e in heap
///pozitia pe care se afla in heap x

void citire();
void Dijkstra();
void inserare(int H[], int & n, int x);
void combinare(int H[], int & n, int poz);
int extrage_minim(int H[], int & n);
void upgrade(int H[], int n, int ppoz);

int main()
{
    citire();
    Dijkstra();
    for (int i = 2; i <= n; i++)
    {
        if (dp[i] == INF)
            fout << 0;
        else
        {
            fout << dp[i] - 1;
        }
        fout << ' ';
    }
    return 0;
}

void citire()
{
    int x, y, c;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        G[x].push_back({y, c});
    }
    for (int i = 0; i <= n; i++)
        dp[i] = INF;
    H[1] = x0;
    nr = 1;
    poz[x0] = 1;
    dp[x0] = 1;
}

void Dijkstra()
{
    int i, j, minim, vfmin;
    for (i = 1; i <= n; i++)
    {
        vfmin = extrage_minim(H, nr);
        if (dp[vfmin] == INF)
            return;
        uz[vfmin] = 1;

        for (j = 0; j < G[vfmin].size(); j++)
        {
            int x = G[vfmin][j].first;
            int cost = G[vfmin][j].second;
            if (!uz[x] && dp[x] > dp[vfmin] + cost)
            {
                dp[x] = dp[vfmin] + cost;
                ///upgrade
                ///promovez varful x in heap pana ajunge la pozitia corecta
                if (poz[x])
                    upgrade(H, nr, poz[x]);
                else
                    inserare(H, nr, x);
            }
        }
    }
}

void inserare(int H[], int & n, int x)
{
    int fiu, tata;
    fiu = n + 1;
    tata = fiu / 2;
    while (tata && dp[H[tata]] > dp[x])
    {
        H[fiu] = H[tata];
        poz[H[tata]] = fiu;
        fiu = tata;
        tata = fiu / 2;
    }
    H[fiu] = x;
    n++;
    poz[x] = fiu;
}

void combinare(int H[], int & n, int ppoz)
///combin H[poz] cu heapurile corecte cu radacinile pe pozitiile 2poz si 2poz+1
{
    int x = H[ppoz], fiu, tata;
    tata = ppoz;
    fiu = 2 * tata;
    while (fiu <= n)
    {
        if (fiu+1 <= n && dp[H[fiu+1]] < dp[H[fiu]])
            fiu++;
        if (dp[H[fiu]] >= dp[x])
            break;
        H[tata] = H[fiu];
        poz[H[fiu]] = tata;
        tata = fiu;
        fiu = 2 * tata;
    }
    H[tata] = x;
    poz[x] = tata;
}

int extrage_minim(int H[], int & n)
{
    int minim = H[1];
    H[1] = H[n];
    n--;
    combinare(H, n, 1);
    return minim;
}

void upgrade(int H[], int n, int ppoz)
{
    int aux;
    int fiu = ppoz, tata = fiu / 2;
    while (tata)
    {
        if (H[fiu] >= H[tata])
            break;
        aux = poz[H[fiu]];
        poz[H[fiu]] = poz[H[tata]];
        poz[H[tata]] = aux;
        aux = H[fiu];
        H[fiu] = H[tata];
        H[tata] = aux;


        fiu = tata;
        tata = fiu / 2;
    }
}