#include <bits/stdc++.h>
#define NMAX 50005
#define mp make_pair
#define oo 1 << 30
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int N;
vector < pair < int, int > > G[NMAX];
int D[NMAX];
bool InCoada[NMAX];
struct comp
{
    bool operator() (int x , int y)
    {
        return D[x] < D[y];
    }
};
priority_queue < int , vector < int > , comp > Q;
void citire()
{
    int M;
    f >> N >> M;
    for(int i = 1 ; i <= M ; i++)
    {
        int x,y,cost;
        f >> x >> y >> cost;
        G[x].push_back(make_pair(y,cost));
    }
}
void Dijkstra()
{
    int NodCurent;
    for(int i = 1 ; i <= N ;i++)
        D[i] = oo;
    D[1] = 0;
    Q.push(1);
    InCoada[1] = true;
    while(!Q.empty())
    {
        NodCurent = Q.top();
        Q.pop();
        InCoada[NodCurent] = false;
        for(auto x : G[NodCurent])
        {
            int Vecin = x.first;
            int Cost = x.second;
            if(D[NodCurent] + Cost < D[Vecin])
            {
                D[Vecin] = D[NodCurent] + Cost;
                if(!InCoada[Vecin])
                {
                    Q.push(Vecin);
                    InCoada[Vecin] = true;
                }

            }
        }

    }
}
void Afis()
{
    for(int i =2 ; i <= N ;i++)
    {
        if(D[i] != oo) g << D[i] <<" ";
        else
            g<< 0 << " ";
    }
}
int main()
{
    citire();
    Dijkstra();
    Afis();
    return 0;
}