#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#define NMax 50000
#define oo 2000000
using namespace std;
ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");
vector <pair<int,int> >G[NMax];
int Distante[NMax];
int N,M;
int minim (int Distante[])
{
    int a,ai;
    a=oo;
    for (int i=2;i<N;i++)
    {
            if (Distante[i]<a)
            {
                ai=i;
                a=Distante[i];
            }
    }
    return ai;
}
void La_Cucaracha (int n,int x)//n->nod, x->cost
{
    unsigned int L=G[n].size();
    for (unsigned int i=0;i<L;i++)
    {
        pair <int,int> aux;
        aux=G[n].at(i);
        if(aux.second+x<Distante[aux.first])
        {
            Distante[aux.first]=aux.second+x;
            int a=minim (Distante);
            La_Cucaracha(a,Distante[a]);
        }
    }
}

int main()
{
    in>>N>>M;
    //Distante.resize(N+2);
    for (int i=0;i<M;i++)
    {
        int A,B,C;
        in>>A>>B>>C;
        pair<int,int>X;
        X.first=B,X.second=C;
        G[A].push_back(X);
    }
    for (int i=1;i<=N;i++)
    {
        Distante[i]=oo;
    }
    La_Cucaracha(1,0);
    for (int i=2;i<=N;i++)
    {
        out<<Distante[i]<<' ';
    }
    return 0;
}