#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct edge{
    int u, v;
    ll w;
};

struct DSU{
    vector<int> parent, r;
    DSU(int n){
        parent.resize(n+1);
        r.resize(n+1, 0);
        for(int i=1; i<=n; i++) parent[i]=i;
    }
    int find(int x){
        if(x==parent[x]) return x;
        return parent[x]=find(parent[x]);
    }
    void unite(int a, int b){
        a=find(a); b=find(b);
        if(a==b) return;
        if(r[a]<r[b]) swap(a, b);
        parent[b]=a;
        if(r[a]==r[b]) r[a]++;
    }
};


int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m; cin>>n>>m;
    vector<edge> e;
    for(int i=0; i<m; i++){
        int u, v; ll w; cin>>u>>v>>w;
        e.push_back({u, v, w});
    }
    sort(e.begin(), e.end(), [](edge a, edge b){
        return a.w<b.w;
    });
    DSU dsu(n);
    ll cost=0;
    vector<pair<int, int>> ans;
    int used=0;
    for(auto x:e){
        if(dsu.find(x.v)!=dsu.find(x.u)){
            dsu.unite(x.u, x.v); ans.push_back({x.u, x.v});
            cost+=x.w;
            used++;
            if(used==n-1) break;
        }
    }
    cout<<cost<<'\n'<<ans.size()<<'\n';
    for(auto [a, b]:ans) cout<<a<<" "<<b<<'\n';



}