#include <bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie{
    int x,y,cost;
} muchii[400001];

int vtati[200001], n, m, cost_total=0, muchii_total=0;
vector<pair<int,int> > noduri_finale;

int cmp(muchie x, muchie y){
    return x.cost < y.cost;
}

int radacina(int x){
    int xi = x, aux;
    while (vtati[xi] != xi){
        xi = vtati[xi];
    }
    while (vtati[x] != x){
        aux = vtati[x];
        vtati[x] = xi;
        x = aux;
        
    }
    return xi;
}

int main()
{
    fin>>n>>m;
    cout<<n<<m;
    for (int i=1; i<=n; i++){
        vtati[i] = i;
    }
    for (int i=1; i<=m; i++){
        int x, y, cost;
        fin>>x>>y>>cost;
        //graf[x].push_back({y,cost});
        //graf[y].push_back({x,cost});
        muchie muchie_;
        muchie_.x = x;
        muchie_.y = y;
        muchie_.cost = cost;
        muchii[i] = muchie_;
        cout<<muchii[i].x<<" "<<muchii[i].y<<" "<<muchii[i].cost<<endl;
    }
    sort(muchii+1, muchii+m+1, cmp);
    for (int i=1; i<=m; i++){
        if (radacina(muchii[i].x) != radacina(muchii[i].y)){
            vtati[radacina(muchii[i].x)] = radacina(muchii[i].y);
            cost_total += muchii[i].cost;
            muchii_total++;
            noduri_finale.push_back({muchii[i].x,muchii[i].y});
        }
    }
    
    fout<<cost_total<<"\n";
    fout<<muchii_total<<"\n";
    for (auto elem: noduri_finale){
        fout<<elem.first<<" "<<elem.second<<"\n";
    }
    
    

    return 0;
}