#include <bits/stdc++.h>

using namespace std;
ifstream r("apm.in");
ofstream w("apm.out");
int v[200002], dim=1, cost[200002], cor[200002], poz[200002], viz[200002];
vector<pair<int, int>>g[200002], rez;
void push(int a)
{
    v[dim]=a;
    poz[a]=dim;
    dim++;
    int ind=dim-1;
    while(ind!=1 && cost[v[ind]]<cost[v[ind/2]])
    {
        swap(v[ind], v[ind/2]);
        swap(poz[v[ind]], poz[v[ind/2]]);
        ind/=2;
    }
}
void pop(int a){
    dim--;
    swap(v[a], v[dim]);
    swap(poz[v[a]], poz[v[dim]]);
    v[dim]=0;
    while(cost[v[a]]>min(cost[v[a*2]], cost[v[a*2+1]]) && a*2<dim){
        if(a*2==dim-1 || cost[v[a*2]] < cost[v[a*2+1]]){
            swap(v[a], v[a*2]);
            swap(poz[v[a*2]], poz[v[a]]);
            a*=2;
        }
        else{
            swap(v[a], v[a*2+1]);
            swap(poz[v[a*2+1]], poz[v[a]]);
            a*=2;
            a++;
        }
    }
}
int main()
{
    int n, m;
    r>>n>>m;
    memset(cost, 0x3f3f3f3f, sizeof(cost));
    cost[1]=0;
    for(int i=1;i<=n;i++){
        push(i);
    }
    for(int i=0; i<m; i++)
    {
        int x, y, c;
        r>>x>>y>>c;
        g[x].push_back(make_pair(y, c));
        g[y].push_back(make_pair(x, c));
    }
    long long sum=0;
    viz[1]=1;
    pop(poz[1]);
    for(int i=0;i<g[1].size();i++){
            if(viz[g[1][i].first]==0 && g[1][i].second<cost[g[1][i].first]){
                cost[g[1][i].first]=g[1][i].second;
                cor[g[1][i].first]=1;
                pop(poz[g[1][i].first]);
                push(g[1][i].first);
            }
        }
    while(rez.size()!=n-1){
        int a=v[1];
        viz[a]=1;
        pop(poz[a]);
        sum+=cost[a];
        rez.push_back(make_pair(a, cor[a]));
        for(int i=0;i<g[a].size();i++){
            if(viz[g[a][i].first]==0 && g[a][i].second<cost[g[a][i].first]){
                cost[g[a][i].first]=g[a][i].second;
                cor[g[a][i].first]=a;
                pop(poz[g[a][i].first]);
                push(g[a][i].first);
            }
        }
    }
    w<<sum<<"\n"<<n-1<<"\n";
    for(int i=0;i<n-1;i++){
        w<<rez[i].first<<" "<<rez[i].second<<"\n";
    }
    return 0;
}