#include<bits/stdc++.h>
using namespace std;
ifstream F("apm.in");
ofstream G("apm.out");
#define P pair<int,int>
priority_queue<P,vector<P>,greater<P> > p;
vector<P> a[200001];
bitset<200001> r;
int n,m,i,j,k,q[200001],z[200001],u,v,w,y;
int main()
{
    for(F>>n>>m;m--;F>>i>>j>>k,a[i].push_back({j,k}),a[j].push_back({i,k}));
    for(i=1;i<=n;q[i]=1e9,++i);
    for(p.push({0,1}),q[1]=0;!p.empty();)
        if(u=p.top().second,p.pop(),!r[u]) {
            r[u]=1,y+=q[u];
            for(auto x:a[u])
                if(v=x.first,w=x.second,!r[v]&&q[v]>w)
                    q[v]=w,p.push({q[v],v}),z[v]=u;
        }
    for(G<<y<<'\n'<<n-1<<'\n',i=2;i<=n;G<<z[i]<<' '<<i<<'\n',++i);
    return 0;
}