#include        <bits/stdc++.h>
#define ll      long long
#define ull     unsigned long long
#define maxn    200005
#define rc(s)   return cout << s,0
#define _       ios_base::sync_with_stdio(false);cin.tie(0);
#define mp      make_pair
#define pii     pair<int,int>
#define endl    '\n'
using namespace std;

const int inf = INT_MAX;

bool viz[maxn];
vector< pii > ans;
vector< pii > vec[maxn];
int sum,n,x,y,z,m,vizited;
priority_queue< pair< int,pii >, vector< pair< int,pii > >, greater < pair< int,pii > > > Q;

void prim()
{
    viz[1] = 1;
    for(int i = 0;i<vec[1].size();i++)
        Q.push(mp(vec[1][i].first,mp(1,vec[1][i].second)));
    while(vizited>0 && !Q.empty())
    {
        while(viz[Q.top().second.first] && viz[Q.top().second.second] && !Q.empty())
            Q.pop();
        if(Q.empty()) break;
        int n1 = Q.top().second.first;
        int n2 = Q.top().second.second;
        ans.push_back(mp(n1,n2));
        sum+=Q.top().first;
        if(!viz[n1]) vizited--;
        if(!viz[n2]) vizited--;
        viz[n1] = 1;
        viz[n2] = 1;
        Q.pop();
        for(int i = 0;i<vec[n1].size();i++)
            if(!viz[vec[n1][i].second]) Q.push(mp(vec[n1][i].first,mp(vec[n1][i].second,n1)));
        for(int i = 0;i<vec[n2].size();i++)
            if(!viz[vec[n2][i].second]) Q.push(mp(vec[n2][i].first,mp(vec[n2][i].second,n2)));
    }
}

int main()
{_
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d",&n,&m);
    vizited = n;
    for(int i = 1;i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&z);
        vec[x].push_back(mp(z,y));
        vec[y].push_back(mp(z,x));
    }
    prim();
    printf("%d\n",sum);
    printf("%d\n",n-1);
    for(int i = 0;i<ans.size();i++) printf("%d %d\n",ans[i].first,ans[i].second);
    return 0;
}