#include <fstream>
#import <algorithm>
#import <vector>
#import <map>
#import <set>
#import <deque>
#import <queue>
#import <cassert>
//#import <cmath>
#import <cstring>
#import <cctype>
#import <cstdlib>
#import <stack>
#import<unordered_map>
using namespace std;
class DSU
{
    vector<int>t;
    int r;
public:
    explicit DSU(int n)
    {
        t.resize(n+1);
        for(int i=1;i<=n;i++)
        {
            t[i]=i;
        }
        r=n;
    }
    int root(int x)
    {
        if(x==t[x])return x;
        t[x]=root(t[x]);
        return t[x];
    }
    bool unite(int a,int b)
    {
        int x=root(a);
        int y=root(b);
        if(x==y)
        {
            return 0;
        }
        r--;
        t[y]=x;
        return 1;
    }

};
struct trei
{
    int x,y,v;
    trei(){};
    explicit trei(int _x,int _y,int _v): x(_x),y(_y),v(_v){}
    bool operator <(trei b)
    {
        return this->v<b.v;
    }
};
main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    int n,m;
    cin>>n>>m;
    DSU dsu(n);
    vector<trei>a(m);
    for(auto &c:a)
    {
        cin>>c.x>>c.y>>c.v;
    }
    sort(a.begin(),a.end());
    int rez=0;
    vector<pair<int,int>>sol;
    for(auto c:a)
    {
        if(dsu.unite(c.x,c.y))
        {
            rez+=c.v;
            sol.push_back({c.x,c.y});
        }
    }
    cout<<rez<<'\n'<<n-1<<'\n';
    for(auto &c:sol)
    {
        cout<<c.first<<' '<<c.second<<'\n';
    }
}