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

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

const int MaxN = 50005;
const int Inf = 0x3f3f3f3f;
VVP G;
int n, m;
int distanta[MaxN];

void Citire();
void Dijkstra(int nod_start);

int main()
{
    Citire();
    for (int i = 1; i <= n; ++i)
        distanta[i] = Inf;
    distanta[1] = 0;

    Dijkstra(1);

    for (int i = 2; i <= n; ++i)
    {
        if (distanta[i] != Inf)
            fout << distanta[i] << ' ';
        else fout << 0 << ' ';
    }
}
void Dijkstra(int nod_start)
{
    priority_queue<P, VP, greater<P> > Q;
    Q.push({distanta[nod_start], nod_start});

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

        Q.pop();

        if (cost_curent > distanta[nod_curent])
            continue;

        for (int i = 0; i < G[nod_curent].size(); ++i)
        {
            int nod_vecin = G[nod_curent][i].first;
            int cost_vecin = G[nod_curent][i].second;

            if (distanta[nod_curent] + cost_vecin < distanta[nod_vecin])
            {
                distanta[nod_vecin] = distanta[nod_curent] + cost_vecin;
                Q.push(make_pair(distanta[nod_vecin], nod_vecin));
            }
        }
    }
}

void Citire()
{
    fin >> n >> m;
    int x, y, z;

    G = VVP(n + 1);

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