#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> muchie;

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

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

class CMP
{
public:
    bool operator()(int a, int b)
    {
        if(d[a] == d[b])
            return a > b;
        return d[a] > d[b];
    }
};

priority_queue<int, vector<int>, CMP> 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});
    }

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

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

        dst = d[nod];
        for(it = v[nod].begin(); it != v[nod].end(); it++)
        {
            mch = *it;
            if(d[mch.fs] > dst + mch.sc)
                d[mch.fs] = dst + mch.sc;
        }
    }

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

    return 0;
}