#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 200005;
const int inf = 2e9 + 2;
priority_queue < pair < int, int > > q;
vector < pair < int, int > > v[NMAX];
int dist[NMAX], viz[NMAX],n,m,from[NMAX], c[NMAX];

int main(){
    int i,j,x,y,z,node;
    f >> n >> m;
    for(i = 1 ; i <= m ; i++){
        f >> x >> y >> z;
        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }

    for(i = 2 ; i <= n ; i++)
        dist[i] = inf;
    q.push({0, 1});
    while(!q.empty()){
        node = q.top().second;
        q.pop();

        if(viz[node])
            continue;
        viz[node] = 1;

        for(auto it : v[node]){
            if(viz[it.first]) continue;
            if(dist[it.first] > it.second){
                dist[it.first] = it.second;
                from[it.first] = node;
                q.push({-dist[it.first], it.first});
            }
        }

    }

    long long ans = 0;
    for(i = 2 ; i <= n ; i++)
        ans += dist[i];

    g << ans << "\n" << n - 1 << "\n";
    for(i = 2 ; i <= n ; i++)
        g << i << " " << from[i] << "\n";
    return 0;
}