#include <iostream>
#include <vector>
#include <fstream>
#include <queue>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector < pair <int, int> >G[50006];
int D[50006];
bool V[50006];
int N, M;
int inf = 999999;

priority_queue <pair <int, int> > myheap;

void citire()
{
    f>>N>>M;

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

void dijkstra(int nod)
{
    myheap.push(make_pair(0,nod));

    for(int i = 1; i <= N; i++)
    {
        D[i] = inf;
        V[i] = 0;
    }

    D[nod] = 0;

    while(!myheap.empty())
    {
        pair <int, int> nodC = myheap.top();
        myheap.pop();
        int k = nodC.second;
        int cost = -nodC.first;

        if(V[k] == 0)
            {
                V[k] = 1;
                D[k] = cost;
                for(int i = 0; i <G[k].size(); i++)
                {
                    int vecin = G[k][i].second;
                    int cst = G[k][i].first;
                    if(cost + cst < D[vecin])
                    {
                        D[vecin] = cst + cost;
                        myheap.push(make_pair(-D[vecin], vecin));
                    }
                }
            }

    }
}

void afisare()
{
    for(int i = 2; i <= N; i++)
        if(D[i] != inf)
            g<<D[i]<<' ';
        else
            g<<'0'<<' ';
}

int main()
{
    citire();
    dijkstra(1);
    afisare();

    return 0;
}