#include <bits/stdc++.h>
#pragma GCC optimize("O1")

using namespace std;

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

const int MAXN = 50005;
const int oo = 0x3f3f3f3f;

vector < pair < int, int > > v[MAXN];
priority_queue < int, vector < int >, greater < int > > pq;

int dist[MAXN];
int viz[MAXN];

int main()
{
    int n, m, a, b, c, nodcurent, nodvecin, i, lim, cost;

    fin >> n >> m;

    while (m--)
    {
        fin >> a >> b >> c;
        v[a].emplace_back(make_pair(b, c));
    }

    memset(dist, oo, sizeof dist);

    pq.push(1);
    dist[1] = 0;
    viz[1] = 1;

    while (!pq.empty())
    {
        nodcurent = pq.top();
        pq.pop();
        viz[nodcurent] = 0;
        lim = v[nodcurent].size();
        for (i = 0; i < lim; ++i)
        {
            nodvecin = v[nodcurent][i].first;
            cost = v[nodcurent][i].second;
            if (dist[nodcurent] + cost < dist[nodvecin])
            {
                dist[nodvecin] = dist[nodcurent] + cost;
                if (!viz[nodvecin])
                {
                    pq.push(nodvecin);
                    viz[nodvecin] = 1;
                }
            }
        }
    }

    for (i = 2; i <= n; ++i)
    {
        if (dist[i] == oo) fout << "0 ";
        else fout << dist[i] << ' ';
    }

    return 0;
}