#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(a*2+1<dim && cost[v[a]]>min(cost[v[a*2]], cost[v[a*2+1]]))
    {
        if(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=a*2+1;
        }
    }
    if(a*2==dim-1 && cost[v[a]]>cost[v[a*2]])
    {
        swap(v[a], v[a*2]);
        swap(poz[v[a*2]], poz[v[a]]);
        a*=2;
    }
}
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(1);
    for(int i=0; i<g[1].size(); i++)
    {
        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;
}