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


using namespace std ;

const int NMAX = 250005 ;
const int INF = 0x3f3f3f3f ;

struct edge
{
    int  b, c;
} aux;

vector <edge> V[NMAX] ;
queue <int> Q ;
vector <int> D(NMAX, INF) ;

int N, M ;

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

inline void DIJKSTRA()
{
    Q.push(1) ;
    D[1] = 0 ;

    while(!Q.empty())
    {

        int nod = Q.front() ;
        Q.pop() ;

        for(int i = 0 ; i < V[nod].size() ; ++ i)
        {
            int cost = V[nod][i].c ;
            int nod_act = V[nod][i].b  ;

            if(D[nod_act] > D[nod] + cost)
            {
                D[nod_act] = D[nod] + cost ;
                Q.push(nod_act) ;
            }

        }
    }

}

inline void READ()
{

    fin >> N >> M ;

    for(int i = 1 ; i <= M ; ++ i)
    {
        int a ;
        fin >> a >> aux.b >> aux.c ;
        V[a].push_back(aux) ;
    }
}

int main()
{
    READ() ;
    DIJKSTRA() ;

    for(int i = 2 ; i <= N ; ++i)
        if(D[i] != INF)
            fout << D[i] << ' ' ;
        else fout << 0 << D[i] << ' ' ;

    fout << '\n' ;

    fin.close() ;
    fout.close() ;
    return  0 ;
}