#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
vector<pair<int,int>> v[50002];
int a[50002],pr[50002];
priority_queue<pair<int,int>> h;
int main()
{
    int n,m,i,nr1,nr2,c,s=0;
    in>>n>>m;
    for(i=0;i<m;i++)
    {
        in>>nr1>>nr2>>c;
        v[nr1].push_back({c,nr2});
        v[nr2].push_back({c,nr1});
    }
    h.push({0,1});
    pr[1]=-1;
    while(!h.empty())
    {
        while(!h.empty()&&pr[h.top().y]>0)
            h.pop();
        if(h.empty())break;
        nr1=h.top().y;nr2=-h.top().x;
        pr[nr1]=-pr[nr1];
        h.pop();
        s+=nr2;
        for(auto it:v[nr1])
            if(pr[it.y]==0||(pr[it.y]<0&&a[it.y]>it.x))
            {
                a[it.y]=it.x;
                pr[it.y]=-nr1;
                h.push({-it.x,it.y});
            }
    }
    out<<s<<"\n"<<n-1<<"\n";
    for(i=2;i<=n;i++)
        out<<pr[i]<<" "<<i<<"\n";
    return 0;
}