#include <iostream>
  
   using namespace std;
  
   const int MAX_N = 100; // maksymalna ilość wierzchołków w grafie
   const int INF = 2147483647;
  
   struct TNode
   {
     int node;            // numer wierzchołka
     int weight;          // waga krawędzi
     struct TNode * next; // następny element listy
   };
  
   main()
   {
     int i,j,u,n,m,x,y,z,v0;
     int d[MAX_N+1],p[MAX_N+1],heap[MAX_N+1],hp[MAX_N+1];
     bool QS[MAX_N+1];
     struct TNode *L[MAX_N+1],*pw;
    
   // Inicjujemy struktury danych
  
     for(i = 1; i <= MAX_N; i++)
     {
       d[i]  = INF;         // koszty dojścia
       p[i]  = 0;           // poprzednik na ścieżce
       QS[i] = false;       // przynależność do Q (false) lub S (true)
       L[i]  = NULL;        // lista sąsiedztwa
       hp[i] = heap[i] = i; // kopiec
     }
     n = 0;
  
   // Odczytujemy dane wejściowe
  
     cin >> v0; // odczytujemy numer wierzchołka startowego
     cin >> m;  // odczytujemy ilość krawędzi
     for(i = 1; i <= m; i++)
     {
       cin >> x >> y >> z; // odczytujemy krawędź
       if(x > n) n = x;
       if(y > n) n = y;
       pw = new TNode;
      
       pw->next = L[x];
       pw->node = y;
       pw->weight = z;
       L[x] = pw;
     }
     cout << endl;
  
     int hlen  = n; // ilość wierzchołków w kopcu
    
     d[v0] = 0;     // koszt dojścia dla v0 jest zerowy
  
   // Odtwarzamy własność kopca
  
     x = heap[1];
     heap[1] = heap[v0];
     heap[v0] = x;
      
     hp[v0] = 1; hp[1] = v0;
      
     for(i = 1; i <= n; i++)
     {
  
       u = heap[1];
      
   // Usuwamy korzeń i odtwarzamy własność kopca
  
       int parent;
      
       heap[1] = heap[hlen];
       hlen--;
      
       hp[heap[1]] = parent = 1;
       while(true)
       {
         int left = parent + parent;
         int right = left + 1;
        
         if(left > hlen) break;
  
         int dmin = d[heap[left]];
         int pmin = left;
  
         if((right <= hlen) && (dmin > d[heap[right]]))
         {
           dmin = d[heap[right]]; pmin = right;
         }
         if(d[heap[parent]] <= dmin) break;
        
         x = heap[parent];
         heap[parent] = heap[pmin];
         heap[pmin] = x;
        
         hp[heap[parent]] = parent;
         hp[heap[pmin]] = pmin;
        
         parent = pmin;
       }
      
   // znaleziony wierzchołek przenosimy do S
  
       QS[u] = true;
  
   // Modyfikujemy odpowiednio wszystkich sąsiadów z Q
      
       pw = L[u];
       while(pw)
       {
         if(!QS[pw->node] && (d[pw->node] > d[u] + pw->weight))
         {
           d[pw->node] = d[u] + pw->weight; p[pw->node] = u;
  
   // Po zmianie d[v] odtwarzamy własność kopca
  
           int child = hp[pw->node];
           while(child > 1)
           {
             parent = child / 2;
             if(d[heap[parent]] <= d[heap[child]]) break;
            
             x = heap[parent];
              heap[parent] = heap[child];
               heap[child] = x;
              
             hp[heap[parent]] = parent;
              hp[heap[child]] = child;
              
             child = parent;
           }
         }
         pw = pw->next;
       }
     }
  
   // Gotowe, wyświetlamy wyniki
  
     int stos[MAX_N],ws;
    
     for(i = 1; i <= n; i++)
     {
       cout << i << ": ";
       ws = 0; j = i;
  
   // Wierzchołki z końca ścieżki umieszczamy na stosie
  
       while(j)
       {
         stos[ws++] = j; j = p[j];
       }
  
   // Wypisujemy kolejne wierzchołki ze szczytu stosu
  
       while(ws) cout << stos[--ws] << " ";
      
   // Wypisujemy koszt dojścia
  
       cout << "#" << d[i] << endl;    
     }        
     char s[1];
     cin.getline(s,1);
     cin.getline(s,1);
   }

  
   struct TNode
     {
       int node;            // numer wierzchołka
       int weight;          // waga krawędzi
       [b]struct TNode * next;[/b] // następny element listy
     };