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

using namespace std;

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> heap;
vector< pair<int, int> > v[50005];
int n, m, x, y, cost, nod, d[50005];
bool ok[50005];

int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    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));
    }
    heap.push(make_pair(1, 0));
    while(!heap.empty())
    {
        while(ok[heap.top().first] && !heap.empty())
            heap.pop();
        if(heap.empty())
            break;
        nod = heap.top().first;
        cost = heap.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)
                heap.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;
}