#include <bits/stdc++.h>

#define INF (1 << 30)
#define LLINF (1LL << 62)
#define mod 666013

#define fs first
#define sc second

using namespace std;

typedef pair<int, int> pereche;

int n, m, i, x, y, z, nod, dst;
int d[50005];
pereche mch;

vector <int> hp;
vector <pereche> v[50005];
vector <pereche> :: iterator it;


bool CMP(int a, int b)
{
    return d[a] > d[b];
}

priority_queue<pereche, vector<pereche>, greater<pereche>> pq;

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

    scanf("%d%d", &n, &m);
    while(m--)
    {
        scanf("%d%d%d", &x, &y, &z);
        v[x].push_back({y,z});
    }

    for(i = 1; i <= n; i++)
        d[i] = INF;
    pq.push({0, 1});

    while(!pq.empty())
    {
        nod = pq.top().sc;
        dst = pq.top().fs;
        pq.pop();

        if(d[nod] != INF)
            continue;
        d[nod] = dst;

        for(it = v[nod].begin(); it != v[nod].end(); it++)
        {
            mch = *it;
            pq.push( {mch.sc + dst, mch.fs} );
        }
    }

    for(i = 2; i <= n; i++)
    {
        if(d[i] == INF)
            d[i] = 0;
        printf("%d ", d[i]);
    }

    return 0;
}