//*******************************
//*        Emil Hotkowski       *
//* Algorytm Dijkstry           *
//* Wersja kopcowa              * 
//* Kopiec własny               *
//* www.algorytm.org            *
//*******************************

#include <stdio.h>
#include <vector.h>
#define N 10000
#define NUM 2000000

using namespace std;
class kopiec{
      public:
      int tab[N];
      int node_nr[N];
      int size;
      kopiec();
      void insert_into(int v,int node);
      void delete_into();
      };
      
bool QS[N];//czy wierzcholek jest juz przerobiony czy nie 
//false oznacza ze juz jest albo jeszcze nie odwiedzono
//true ze ma jakas wartosc ale czeka w kopcu
vector <vector<int> > waga(N);//tablica vectorow (graf)
vector <vector<int> > graf(N);//-||-  (wagi)

int main()
{
    int n,m;//ilosc krawedzi !!!
    scanf("%d %d",&n,&m);//wczytuje ilosc wierzcholkow i krawedzi
    int * wartosc = new int [n+1] ;//tablica na wartosci
    
   for(int i = 0 ; i <= n ;i++)wartosc[i]=NUM;//wypelniam je duzym czyms
   
   
    for(int i = 1 ; i <= m;i++){
            int a,b,w;
            scanf("%d %d %d",&a,&b,&w);//wczytuje 
            graf[a].push_back(b);//wypelniam krawiedzi
            waga[a].push_back(w);//i wagi
       }
 
    wartosc[1]=0;   //wierzcholek nr 1
    QS[1]=false;    //juz odwiedzony
    kopiec K;       //nasz kopiec
    int ii = 1;     //aktualny wierzcholek na ktorym sie poruszamy
    for(int x = 1 ; x <= n ; x++){//wszystkie wierzchołki

            while(!graf[ii].empty()){//dopoki nie odwiedzimy wsyzstkich krawedzi wychodzacych z wierzchołka
    
            int z = graf[ii].back();//numer wierzchołka do ktorego mamy krawedz
            if(wartosc[z] > wartosc[ii]+waga[ii].back()){//sprawdzamy czy da sie poprawic droge , jezeli tak
                         wartosc[z] = wartosc[ii] + waga[ii].back(); //poprawiamy
                         QS[z]=true;//wierzchołek do kopca
                         K.insert_into(wartosc[z],z);//insert do kopca
                         
                          }//if waga
                          waga[ii].pop_back();//usuwamy wage
                          graf[ii].pop_back();//usuwamy wierzcholek
            }
            ii = K.node_nr[1];//sprawdzamy kolejny wierzcholek z najlżejszą drogą
            K.delete_into();//usuwamy go z kopca , ew czyscimy z nadmiaru wierzchołkow dublowanych
            }
   for(int i = 1 ; i <= n ; i++)printf("%d : %d\n",i,wartosc[i]);//wyswietlamy min drogi
   
    return 0;
}


kopiec::kopiec(){
                 size = 0;
                 }

void kopiec::insert_into(int v,int node){
       tab[size+1] = v;
       int s = size+1;
       node_nr[s] = node;
       while(s!=1)
       {
       if(tab[s/2] > tab[s]){
                   tab[s]=tab[s]^tab[s/2];
                   tab[s/2]=tab[s]^tab[s/2];
                   tab[s]=tab[s]^tab[s/2];
                   node_nr[s]=node_nr[s]^node_nr[s/2];
                   node_nr[s/2]=node_nr[s]^node_nr[s/2];
                   node_nr[s]=node_nr[s]^node_nr[s/2];
                   s/=2;}
       else break;
       }
       
       size++;
       }

void kopiec::delete_into(){
       tab[1] = tab[size];
       size--;
       int tmp = 1;
       while(tmp*2 <= size){
              if(tab[tmp] > tab[tmp*2] || tab[tmp] > tab[tmp*2+1])
              {
              if(tab[tmp*2] < tab[tmp*2+1] || tmp*2+1 > size){
                            
                           tab[tmp]=tab[tmp]^tab[tmp*2];
                           tab[tmp*2]=tab[tmp]^tab[tmp*2];
                           tab[tmp]=tab[tmp]^tab[tmp*2];
                           node_nr[tmp]=node_nr[tmp]^node_nr[tmp*2];
                           node_nr[tmp*2]=node_nr[tmp]^node_nr[tmp*2];
                           node_nr[tmp]=node_nr[tmp]^node_nr[tmp*2];
                            tmp=tmp*2;
                            
                            }
              else{
                   
                           tab[tmp]=tab[tmp]^tab[tmp*2+1];
                           tab[tmp*2+1]=tab[tmp]^tab[tmp*2+1];
                           tab[tmp]=tab[tmp]^tab[tmp*2+1];
                           node_nr[tmp]=node_nr[tmp]^node_nr[tmp*2+1];
                           node_nr[tmp*2+1]=node_nr[tmp]^node_nr[tmp*2+1];
                           node_nr[tmp]=node_nr[tmp]^node_nr[tmp*2+1];
                   tmp=tmp*2+1;} 
              }
              else {QS[tmp]=false;break;}
       }
       if(QS[node_nr[1]]==false)delete_into();
       }