#include <fstream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
unordered_map<int,int> parent;
unordered_map<int,int> sz;
struct muchie
{
    int x,y; int cost;
}; vector<muchie> graph;
vector<pair<int,int>> sol;
bool cmp(muchie a,muchie b)
{
    return a.cost<b.cost;
}
void make_group(int x)
{
    if(parent.find(x)==parent.end())
    {
        parent[x]=x;
        sz[x]=1;
    }
}
int reprezentant(int x)
{
    if(parent[x]==x)return x;
    return parent[x]=reprezentant(parent[x]);
}
bool union_(int x,int y)
{
    make_group(x); make_group(y);
    int rx=reprezentant(x),ry=reprezentant(y);
    if(rx==ry) return 0;
    if(sz[rx]<sz[ry]) swap(rx,ry);
    parent[ry]=rx;
    sz[rx]+=sz[ry]; return 1;
}
int main()
{
    int n,m; cin>>n>>m;
    graph.resize(m);
    for(int i=0;i<m;i++){
        int u,v,z; cin>>u>>v>>z;
        graph[i].x=u;
        graph[i].y=v;
        graph[i].cost=z;
    }
    sort(graph.begin(),graph.end(),cmp);
    int u=graph[0].x,v=graph[0].y;
    sol.push_back({u,v}); int sum=graph[0].cost;
    int ct=1;
    if(ct==n-1) {
        cout<<sum<<'\n'<<n-1<<'\n';
        cout<<u<<" "<<v; return 0;
     }
    bool ok=union_(u,v);
    for(int i=1;i<m;i++){
        int a=graph[i].x, b=graph[i].y;
        if(union_(a,b)) {
            sol.push_back({a,b});
            sum+=graph[i].cost;
            ct++;
        }
        if(ct==n-1) break;
    }
    cout<<sum<<'\n'<<n-1<<'\n';
    for(auto l:sol) cout<<l.first<<" "<<l.second<<'\n';
    return 0;
}