#include <iostream>
#include <fstream>
#include <queue>
#include <list>
#include <vector>
#include <functional>
using namespace std;

const int max_orase = 50001;
const int max_drumuri = 250001;
const int max_pokemoni = 20;
const int max_schimbari = 20;


typedef pair<int,int> oras;
typedef struct d_nod
{
    int unde;
    int cost;
} vecin;


ifstream in;
ofstream out;
int N, M, P, K;
int distante[max_orase];
int vizitati[max_orase];
int nr_mare = 2147483647;

list<vecin> vecinii[max_orase];
priority_queue<oras, vector<oras>, greater<oras> > coada;

void citeste();
void dijkstra();

int main()
{
    citeste();
    dijkstra();
    out.open("dijkstra.out");

    for( int i = 2; i <= N; i++ )
    {
        if ( distante[i] == nr_mare )
        distante[i] = 0;
        out << distante[i] << " ";
    }

    out.close();

    return 0;
}

void dijkstra()
{
    distante[1] = 0;
    oras nou,temp;
    nou.first = 0;
    nou.second = 1;
    coada.push(nou);
    vizitati[1] = 1;

    while( !coada.empty() )
    {
        temp = coada.top();
        coada.pop();
        vizitati[temp.second] = 1;
        for( list<vecin>::iterator it = vecinii[temp.second].begin(); it != vecinii[temp.second].end(); it++ )
        {
            if( distante[it->unde] > distante[temp.second] + it->cost )
            {
                distante[it->unde] = distante[temp.second] + it->cost;
                //if( vizitati[it->unde]  != 1 )
                //{
                    nou.first = distante[it->unde];
                    nou.second = it->unde;
                    coada.push(nou);
                //}

            }
        }
    }
}

void citeste()
{
  in.open("dijkstra.in");
  in >> N >> M;
  for( int i = 0; i <= N; i++ )
    distante[i] = nr_mare;
  vecin citire;
  int x,y,c;
  for( int i = 0; i < M; i++ )
  {
    in >> x >> y >> c;
    citire.cost = c;
    citire.unde = y;
    vecinii[x].push_back(citire);
    citire.unde = x;
    vecinii[y].push_back(citire);
  }
  in.close();
}