#include <bits/stdc++.h>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
#define pb push_back
#define mp make_pair
const int MAXN=400001;
int n,m;
int ver[MAXN];
vector<int>g[MAXN],g1[MAXN];
vector <pair<int,pair<int,int>>>gu;
vector <pair<int,int>>gs;
int father[MAXN];
int s[MAXN];
int Find(int x){
    if(father[x]==x)
        return x;
    return father[x]=Find(father[x]);
}
void Union(int x,int y){
    int a=Find(x);
    int b=Find(y);
    if(a!=b)
    if(s[a]>s[b])
        swap(a,b);
        father[a]=b;
        s[b]+=s[a];

}
int main()
{
    in>>n>>m;
    int x,y,c;
    for(int i=0;i<m;i++){
        in>>x>>y>>c;
        g[x].pb(y);
        g[y].pb(x);
        gu.pb(mp(c,mp(x,y)));
    }
    int nr=n,ans=0;
    memset(s,1,sizeof(s));
    for(int i=1;i<=n;i++)
        father[i]=i;
    sort(gu.begin(),gu.end());
    for(int i=0;i<m;i++){
        int cost=gu[i].first;
        x=gu[i].second.first;
        y=gu[i].second.second;
        if(father[x]!=father[y]){
            Union(x,y);
            gs.push_back(mp(x,y));
            nr--;
            ans+=cost;
        }
        if(nr==1)
            break;
    }
    out<<ans<<'\n'<<n-1<<'\n';
    for(auto y:gs)
    out<<y.first<<' '<<y.second<<'\n';
    return 0;
}