#include <bits/stdc++.h>
using namespace std;
int FindSet(vector<int> &t, int x)
{
    while(x != t[x])
        x = t[x];
    return x;
}
void UnionSet(int x, int y, vector<int> &t, vector<int> &h)
{
    int xSet = FindSet(t,x), ySet = FindSet(t,y);
    if(h[xSet] < h[ySet])
        t[xSet] = ySet;
    else
    {
        t[ySet] = xSet;
        if(h[xSet] == h[ySet]) h[xSet]++;
    }
 }
int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");
    vector<pair<int, pair<int,int> > > G;
    vector<bool> viz;
    vector<int> t;
    vector<int> h;
    int n, m, sum = 0, cnt = 0;
    in>>n>>m;
    G.resize(m+1);
    viz.resize(m+1);
    t.resize(n+1);
    h.resize(n+1);
    for(int i=1; i<=n; i++)
        t[i] = i;
    for(int i=1; i<=m; i++)
        in>>G[i].second.first>>G[i].second.second>> G[i].first;
    sort(G.begin()+1,G.end());
    for(int i=1; i<=m && cnt < n-1; i++)
        if(FindSet(t, G[i].second.first) != FindSet(t, G[i].second.second))
        {
            viz[i] =  1;
            UnionSet(G[i].second.first,G[i].second.second, t, h);
            sum += G[i].first;
            cnt++;
        }
    out<<sum<<'\n'<<cnt<<'\n';
    for(int i=1; i<=m; i++)
        if(viz[i])
            out<<G[i].second.first<<" "<<G[i].second.second<<'\n';
    return 0;
}