#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int NMAX = 50002;
vector < pair <int, int> > v[NMAX];
set < pair <int, int> > q;
int dist[NMAX], N, M;
int main()
{
    fill_n(dist, NMAX, INT_MAX);
    dist[1] = 0;
    fin >> N >> M;
    int a, b, c;
    for (int i = 1; i <= M; i++)
    {
        fin >> a >> b >> c;
        v[a].push_back(pair<int, int>(b, c));
    }
    int x;
    for (auto i : v[1]) {
        q.insert( pair <int, int>(i.second, i.first));
    }
    q.insert(pair <int, int>(0, 1));
    while (!q.empty())
    {
        x = q.begin()->second;
        q.erase(q.begin());
        for (auto i : v[x])
        {
            if (dist[x] + i.second < dist[i.first])
            {
                q.erase(pair<int, int>(i.second, i.first));
                dist[i.first] = dist[x] + i.second;
                q.insert(pair<int, int>(i.second, i.first));
            }
        }
    }
    for (int i = 2; i <= N; i++)
        fout << (dist[i] == INT_MAX ? 0 : dist[i]) << " ";
    return 0;
}