#include <bits/stdc++.h>
#define ull unsigned long long
#define FILES freopen("apm.in","r",stdin);\
              freopen("apm.out","w",stdout);
#define CMAX 1000000
#define fastio std::ios_base::sync_with_stdio(NULL),cin.tie(NULL),cout.tie(NULL);
#define mp make_pair
#define INF 999999999999999
#define void inline void
#define mod 1000000007
#define ll long long
#define MAX 200000
#define SMAX 500000
#define pb push_back
#define add emplace_back
using namespace std;
struct solve
{
    int first,second,third;
};
int n,m,root[MAX+5];
set<int> s;
unordered_map<int,int> Fr;
vector<solve> Qs;
bool cmp(solve a,solve b)
{
    return a.third < b.third;
}
int Find(int x)
{
    if(x != root[x]) return root[x] = Find(root[x]);
    else return x;
}
void read(int &a)
{
    a = 0;
    char c;
    bool minus = false;
    while(1)
    {
        c = getchar();
        if(c == '-')
        {
            minus = 1;
            continue;
        }
        if(c < '0' || c > '9') break;
        a = a * 10 + c - '0';
    }
    if(minus) a = -a;
}
int main()
{
    fastio
    FILES
    read(n),read(m);
    for(int i = 1; i <= n; ++i) root[i] = i;
    for(int i = 1; i <= m; ++i)
    {
        int a,b,c;
        read(a),read(b),read(c);
        Qs.pb({a,b,c});
    }
    vector<solve> ans;
    sort(Qs.begin(),Qs.end(),cmp);
    int p = 0,cost = 0;
    for(int i = 0; i < Qs.size(); ++i)
    {
        int r = Find(Qs[i].first),r2 = Find(Qs[i].second);
        if(r == r2) continue;
        if(r != r2)
        {
            if(r > r2) root[r] = r2;
            else root[r2] = r;
            p++,cost += Qs[i].third;
            ans.pb({Qs[i].first,Qs[i].second});
        }
    }
    cout << cost << '\n' << p << '\n';
    for(int i = 0; i < ans.size(); ++i)
        cout << ans[i].first << ' ' << ans[i].second << '\n';
}