#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

struct cmp
{
    bool operator()(pair<int, int> a, pair<int, int> b)
    {
        return a.second > b.second;
    }
};

priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> h;

vector<pair<int, int>> v[50010];

int n, m, x, y, cost, nod, d[50010];

bool ok[5005];

int main()
{
    fin >> n >> m;
    for(int i = 2; i <= n; i++)
        d[i] = 2000000000;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        v[x].push_back(make_pair(y, cost));
    }

    h.push(make_pair(1, 0));

    while(!h.empty())
    {
        while(ok[h.top().first] && !h.empty())
            h.pop();

        if(h.empty())
            break;

        nod = h.top().first;
        cost = h.top().second;
        ok[nod] = 1;
        d[nod] = cost;

        for(int i = 0; i < v[nod].size(); i++)
            if(!ok[v[nod][i].first] && d[v[nod][i].first] > d[nod]+v[nod][i].second)
                h.push(make_pair(v[nod][i].first, d[nod] + v[nod][i].second));
    }

    for(int i = 2; i <= n; i++)
        fout << (d[i] != 2000000000 ? d[i] : 0) << " ";

    return 0;
}