#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho10
#define ll long long
#define double long double
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#define sz size
#define f first
#define s second
#define pb push_back
#define er erase
#define in insert
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 1000000007
#define PI 3.14159265359
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005ll
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll n,m,p[200005],s[200005],sum=0;
pair<ll,pair<ll,ll>>g[200005];
vector<pair<ll,ll>>ans;
ll caut(ll x){
if(x==p[x]){
    return x;
}else return p[x]=caut(p[x]);
}
void uni(ll x,ll y){
x=caut(x);
y=caut(y);
if(x!=y){
    if(s[x]<s[y]){
        swap(x,y);
    }
    p[y]=x;
    s[x]+=s[y];
}
}
int32_t main(){
CODE_START;
ifstream cin("apm.in");
ofstream cout("apm.out");
cin>>n>>m;
for(ll i=1;i<=n;i++)
{
    p[i]=i;
}
for(ll i=1;i<=m;i++)
{
    cin>>g[i].s.f>>g[i].s.s>>g[i].f;
}
sort(g+1,g+m+1);
for(ll i=1;i<=m;i++)
{
    ll x=g[i].s.f,y=g[i].s.s;
    if(caut(x)!=caut(y)){
        uni(x,y);
        sum+=g[i].f;
        ans.pb(mp(x,y));
    }
}
cout<<sum<<endl;
cout<<n-1<<endl;
for(auto it : ans){
    cout<<it.f<<' '<<it.s<<endl;
}
}