#include <bits/stdc++.h>
#define oo 1<<30
using namespace std;

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

 ///                cost  nod
priority_queue< pair<int, int> > q;
bool viz[50003];
int d[50003]; /// d[i] = distanta minima de la 1 la i
int n, m;
 ///         cost  nod
vector< pair<int, int> > h[50003];

int main()
{
    int k, i, j, c;
    fin >> n >> m;
    for (k = 1; k <= m; k++)
    {
        fin >> i >> j >> c;
        h[i].push_back({c, j});
    }
    /// init d:
    for (i = 2; i <= n; i++)
        d[i] = oo;
    /// Dijkstra : O(n x log n)
    q.push({0, 1});
    while (!q.empty())
    {
        k = q.top().second;
        q.pop();
        if (!viz[k])
        {
            viz[k] = true;
            for (auto e : h[k])
            {
                i = e.second;
                c = e.first;
                if (d[i] > d[k] + c) /// relaxare
                {
                    d[i] = d[k] + c;
                    q.push({-d[i],i});
                }
            }
        }
    }
    for (i = 2; i <= n; i++)
        if (d[i] < oo) fout << d[i] << " ";
        else fout << "0 ";
    return 0;
}