#include <iostream>
#include <fstream>

using namespace std;

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

struct nod
{
    nod * next ;
    int info ;
    int cost ;
} ;

int N , M ;
nod * L [50001] ;

void Add ( int , int , int ) ;
void Citire()
{
    int a , b , c  , copie ;
    fin >> N >> M ;
    copie = M ;
    while ( copie >= 1 )
    {
        fin >> a >> b >> c ;
        Add ( a , b , c ) ;
        -- copie ;
    }
}

void Add ( int a , int b , int c )
{
    nod * p = new nod ;
    p->info = b ;
    p->cost = c ;
    p->next = L[a] ;
    L[a] = p ;
}

int h[50001] , d[50001] , t[50001] , p[50001] , nd ;
// h = heap care mentine consturile de la nodul 1 la nodul i ;
// d [i] = costul drumului de la nodul 1 la nodul i  .... caut minimizarea acestuia
// t [i] = predecesorul , tatal nodului i pe drumul de la 1 la i
// p [i] = pozitia nodului i in HEAP

void intersch ( int i , int j )
{
    int aux ;
    // Interschimbare valori in heap
    aux = h [i] ;
    h [i] = h [j] ;
    h [j] = aux ;
    // Interschimbare pozitii
    aux = p [ h [i] ] ;
    p [ h [i] ] = p [ h [j] ] ;
    p [ h [j] ] = aux ;

}

void heapup ( int i ) //se reface HEAP -ul ( doar partea de deasupra fiului ) ;
{
        if ( d[ h[i/2] ] < d[ h[i] ] )return;
        intersch ( i , i/2 ) ;
        heapup ( i/2 ) ;
}

void heapdown ( int i ) // se reface proprietatea de heap , se reordoneaza arborele
{
        int fiust , fiudr ;
        if ( 2 * i <= N )
               fiust = d [ h[i*2] ];

        if ( i * 2 + 1 <= N )
             fiudr = d [ h[ i * 2 + 1 ] ] ;
        else
             fiudr = fiust + 1 ;

        if ( fiust < fiudr )
        {
                if ( d [ h[i] ] <= fiust ) // verifica ca parintele sa fie mai mic decat cel mai mic fiu
                        return;
                intersch ( i , 2 * i ) ;
                heapdown ( i * 2 ) ;
        }
        else
        {
                if ( d [h[i] ] <= fiudr )
                          return;
                intersch ( i , 2 * i + 1 ) ;
                heapdown ( 2 * i + 1 ) ;
        }
}

void scrie (int x)
{
        if ( x != 1 && x != 0 )
               scrie ( t [x] );
        cout << x << " " ;
}


int main()
{
    Citire () ;
    int i ;
    for ( i = 1 ; i <= N; ++ i )
        {
                d[i] = 2000000000; /*Initial toate distantele sunt considerate infinit*/
                h[i] = i;
                p[i] = i;
        }
    d [1] = 0 ;
    d [0] = -1 ;
    nod * q = new nod ;

    M = N ;
    for ( i = 0 ; i < N ; ++ i)
        {
                nd = h[1] ;   // Desemnam nodul pe care il expandam
                intersch ( 1 , M ) ;  // Dupa ce am ales nodul pe care il expanda, (cel din varful heapupul) il mutam la coada
                -- M ; // si scadem lungimea heapului, astfel incat algoritmul va lasa nodul curent in pace
                heapdown (1) ; // Refacem prop de HEAP
                for ( q = L [nd] ; q != 0 ; q = q->next ) //Luam fiecare nod vecin cu cel pe care il expandam
                        if ( d [q->info] > d [nd] + q->cost ) //Verificam daca ajungem la el cu un cost mai bun
                        {
                                d [q->info] = d [nd] + q->cost ; //Daca da, actualizam distanta,
                                t [q->info] = nd ; // desemnam nodul curent ca fiind noul tata al nodului pe care l-am actualizat
                                heapup ( d[q->info] ) ; //si reordonam heapul
                        }
        }
        // Afisare
        for ( i = 2 ; i <= N ; ++ i )
                if ( d[i] == 2000000000 )
                        cout<<"Nu se poate ajunge la nodul "<<i<<" " ;// Daca are costul infinit ( adica 2000000000, asa cum am initializat mai sus, inseamna ca nu s-a putut ajunge la nod
                else
                        {
                                cout << "Nodul "<<i<<" Costul "<< d[i]<<"\n" ;
                                fout << d[i] << " " ;
                                scrie ( t[i] ) ;
                                cout << "\n" ;
                        }
    return 0;
}