#include <fstream>
#include <bits/stdc++.h>

#define NMAX 200005
#define inf 99999999

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct cmp{
    bool operator()(pair <int,int> x , pair <int,int> y){
        return x.second>y.second;}
    };

vector <pair<int, int> > adj[NMAX];

priority_queue <pair<int, int>, vector<pair<int, int>>, cmp> q;

int main(){
    int n, m, x, y, c;
    f >> n >> m;
    vector <int> d(n + 1, inf);
    vector <bool> viz(n + 1, false);
    vector <int> p(n + 1, 0); 

    for(int i = 0; i < m; i ++){
        f >> x >> y >> c;
        adj[x].push_back(make_pair(y, c));
        adj[y].push_back(make_pair(x, c));
    }

    q.push(make_pair(1, 0));
    d[1] = 0;


    while(!q.empty()){
        auto u = q.top();
        q.pop();
        if (viz[u.first]) 
            continue;
        viz[u.first] = true;
        for (auto v : adj[u.first]){
            if (viz[v.first])
                continue;
            if (d[v.first] > v.second){
                d[v.first] = v.second;
                p[v.first] = u.first;
                q.push(v);
            }
        }
    }

    int s = 0;
    for(int i = 1; i <= n; i ++){
        s += d[i];
    }

    g << s << " " << n - 1 << '\n';

    for(int i = 2; i <= n; i++){
        g << p[i] << " " << i << '\n';
    }

    





}