#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int main()
{
    int n, m;
    fin >> n >> m;

    vector<int>dist(n+1, 1005);
    vector<int>tata(n+1);
    vector<vector<pair<int, int>>>adj(n+1);

    for(int i = 0; i < m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;

        adj[x].push_back({y, c});
        adj[y].push_back({x, c});

    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<bool>visited(n+1);

    pq.push({0, 1});
    int cost = 0;
    int cnt = 0;
    while(!pq.empty() && cnt < n)
    {
        auto f = pq.top();
        pq.pop();

        if(!visited[f.second])
        {
            cost+= f.first;
            cnt++;
        visited[f.second] = true;

        for(auto a : adj[f.second])
        {
            if(visited[a.first] != true && a.second < dist[a.first])
            {
                dist[a.first] = a.second;
                tata[a.first] = f.second;
                pq.push({dist[a.first], a.first});
            }
        }
        }
    }

    fout << cost << "\n" << n - 1 << "\n";
    for(int i = 2; i <= n; i++)
        fout << i << " " << tata[i] << "\n";
    return 0;
}