#include <iostream>
#include <set>
#include <vector>
#include <fstream>
#define MAX_INT 999999

using namespace std;

int dist[50001];
vector< vector< pair<int, int> > >graph;

void addEdge(int from, int to, int weight){
    graph[from].push_back( make_pair(to,weight) );
    graph[to].push_back(make_pair(from,weight));
}

void shortestPath(int startNode, int N){
    ofstream ki("dijkstra.out");
    set< pair<int,int> > minSet;
    minSet.insert(make_pair(0,startNode));
    dist[startNode] = 0;
    while(!minSet.empty()){
        pair<int,int> temporary = *( minSet.begin() );
        minSet.erase(minSet.begin());
        int currentNode = temporary.second;
        cout <<" currentNode: "<< currentNode <<" : ";
        for(int i = 0; i < graph[currentNode].size(); i++){
            int node = graph[currentNode][i].first;
            cout << node << " ";
            int weight = graph[currentNode][i].second;
            if(dist[node] > dist[currentNode] + weight){
                if(dist[node] != MAX_INT)
                    minSet.erase(minSet.find(make_pair(dist[node], node)));
                dist[node] = dist[currentNode] + weight;
                minSet.insert(make_pair(dist[node], node));
            }
        }
         cout << endl;
    }
    for(int i = 1; i < N; i++)
        ki << dist[i] <<" ";
}

int main()
{
    int n, m, a, b, c;
    ifstream be("dijkstra.in");
    be>>n>>m;
    cout <<n<<" "<<m<<endl;
    vector< pair<int,int> > eVec;
    for(int i = 0; i < n; i++){
        graph.push_back(eVec);
        dist[i] = MAX_INT;
    }
    for(int i=0; i<m; i++){
        be>>a>>b>>c;
        cout << a<< " "<<b<<" "<<c<<endl;
        addEdge(a-1,b-1,c);
    }
    shortestPath(0, n);
}