/// HIP = priority queue(STL)
/// http://www.infoarena.ro/problema/dijkstra
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define N 50005

using namespace std;

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

const int       oo = 1 << 30;

vector          <pair <int, int> > g[N];
priority_queue  <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > H;
int             n, m, c[N];

/// n - noduri, m - legaturi intre noduri, C[] - vectorul de costuri

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n; i++)
        c[i] = oo;
    for (int x, y, cost, i = 0; i < m; i++)
    {
        fin >> x >> y >> cost;
        g[x].push_back(make_pair(y, cost));

    }
    H.push(make_pair (0, 1)); /// (c[i], i)
    c[1] = 0;
    while (H.size())
    {
        int     cost = H.top().first;
        int     x = H.top().second;

        H.pop();
        //if (cost > c[x])
        //    continue;
        if (!(cost > c[x]))
        {
            for (int i = 0; i < g[x].size(); i++)
            {
                if (c[g[x][i].first] > cost + g[x][i].second)
                {
                    c[g[x][i].first] = cost + g[x][i].second;
                    H.push(make_pair (cost + g[x][i].second, g[x][i].first));
                }
            }
       }
    }
    for (int i = 2; i <= n; i++)
    {
        if (c[i] == oo)
            gout << "0 ";
        else
            gout << c[i] << ' ';
    }
    return 0;
}