#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define P pair<int, int>
#define VVP vector<vector<P> >
using namespace std;

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

const int MaxN = 50005;
const int Inf = 0x3f3f3f3f;

int n, m;
int dist[MaxN];
VVP G;

void Citire();
void Dijkstra(int nod);

int main()
{
    Citire();
    Dijkstra(1);
    for (int i = 2; i <= n; ++i)
    {
        if (dist[i] != Inf)
            fout << dist[i] << ' ';
        else
            fout << 0 << ' ';
    }
}

void Dijkstra(int nod)
{
    priority_queue<P, vector<P>, greater<P> > Q;
    Q.push(make_pair(dist[nod], nod));

    while(!Q.empty())
    {
        int cost_curent = Q.top().first;
        int nod_curent = Q.top().second;

        Q.pop();

        if (dist[nod_curent] < cost_curent)
            continue;

        for (int i = 0; i < G[nod_curent].size(); ++i)
        {
            int vecin = G[nod_curent][i].first;
            int cost_vecin = G[nod_curent][i].second;
            if (dist[vecin] > dist[nod_curent] + cost_vecin)
            {
                dist[vecin] = dist[nod_curent] + cost_vecin;
                Q.push(make_pair(cost_vecin, vecin));
            }
        }
    }
}

void Citire()
{
    fin >> n >> m;
    G = VVP(n + 1);

    for (int i = 1; i <= m; ++i)
    {
        int x, y, w;
        fin >> x >> y >> w;
        G[x].push_back(make_pair(y, w));
    }

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