#include <iostream>
#include <fstream>
#include <queue>
#include <list>
#include <vector>
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];

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

void citeste();
void dijkstra();

int main()
{
    citeste();
    dijkstra();
    out.open("dijkstra.out");
    for( int i = 2; i <= N; i++ )
        out << distante[i] << " ";
    out.close();

    return 0;
}

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

    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;
                cout << distante[it->unde] << endl;
                if( vizitati[it->unde] != 1 )
                {
                    nou.first = distante[it->unde];
                    nou.second = it->unde;
                    coada.push(nou);
                }
            }
        }
    }
}

void citeste()
{
  in.open("pokemon.in");
  in >> N >> M;
  int nr_mare = 1 << 30;
  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);
  }
  in.close();
}