/*
Find single source shortest path - Dijkstra's algo
and print the distance as well as path
Input:
n-vertices , m-edges
u , v , w - undirected edge with weight w
9 14
0 1 4
0 7 8
1 7 11
1 2 8
7 8 7
7 6 1
2 8 2
8 6 6
2 3 7
2 5 4
6 5 2
3 5 14
3 4 9
5 4 10

Output:
vertex distance Path
0 -> 1	4		0 1
0 -> 2	12		0 1 2
0 -> 3	19		0 1 2 3
0 -> 4	21		0 7 6 5 4
0 -> 5	11		0 7 6 5
0 -> 6	9		0 7 6
0 -> 7	8		0 7
0 -> 8	14		0 1 2 8

Time Compexity : O(E logV)
using multiset as min priority queue

*/
#include<bits/stdc++.h>
using namespace std;

#define INF 1000000000

void printPath(vector<int> &parent, int j)
{
    // Base Case : If j is source
    if (parent[j]==-1)
	{
		cout<< j << " ";
		return ;
	}


    printPath(parent, parent[j]);

    cout<< j << " ";
}

void dijkstra(vector<vector<pair<int , int>>> &adj , vector<int> &dist ,
vector<int> &vis , vector<int> &parent){

    multiset < pair < int , int > > s; // multiset do the job as a min-priority queue
    s.insert({0 , 0}); // insert the source node with distance = 0
    parent[0] = -1 ;
    dist[0] = 0;

    while(!s.empty()){

        pair <int , int> p = *s.begin(); // pop the vertex with the minimum distance
        s.erase(s.begin());

        int u = p.second;

        if( vis[u] ) continue; // check if the popped vertex is visited before

        vis[u] = true;

        for(int i = 0; i < adj[u].size(); i++)
        {
            int v = adj[u][i].second; int w = adj[u][i].first;

            if(!vis[v] && dist[u] + w < dist[v] )
            {
            	// check if the next vertex distance could be minimized
	            dist[v] = dist[u] + w;
	            s.insert({dist[v], v} ); // insert the next vertex with the updated distance
	            parent[v] = u ;
            }
        }
    }
}

int main(){

    int n,m,u,v,w;
    cin>>n>>m; //Nodes and edges.
    vector<vector<pair<int , int>>> adj(n) ;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v>>w;
        adj[u].push_back(make_pair(w,v)); //undirected graph
        adj[v].push_back(make_pair(w,u));
    }

    vector<int> dist(n , INF ) ;
    vector<int> vis(n , false) ;
    vector<int> parent(n , -1) ;

    dijkstra(adj , dist , vis , parent);

    for(int i=1;i<n;i++)
    {
    	cout<< 0 << " -> " << i << "\t" ;
    	cout<<dist[i]<<"\t";
    	printPath(parent , i) ;
    	cout<<endl ;
    }
    return 0;
}