#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

const int NMAX = 5 * 1e4 + 1;
const int INF = INT_MAX;

int dist[NMAX];
vector <pair<int, int> > a[NMAX];

void dijkstra(pair<int, int> sursa)
{
    priority_queue <pair <int, int>, vector<pair <int, int> >, greater<pair<int, int> > > pq;
    pq.push(sursa);

    while(!pq.empty())
    {
        int nod, val;
        nod = pq.top().second;
        val = pq.top().first;

        pq.pop();

        for(auto x: a[nod])
            if(x.first + val < dist[x.second])
            {
                dist[x.second] = x.first + val;
                pq.push(make_pair(dist[x.second], x.second));
            }
    }
}

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

    int n, m;
    fin >> n >> m;

    for(int i = 0; i < m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        a[x].push_back(make_pair(c, y));
    }

    for(int i = 2; i <= n; i++)
        dist[i] = INF;

    dijkstra(make_pair(0, 1));

    for(int i = 2; i <= n; i++)
        fout << dist[i] << " ";

    return 0;
}