#include <bits/stdc++.h>
#define maxN 200010
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

vector<pair<int,int>> G[maxN], rez;
priority_queue<pair<int,int>> Q;
int viz[maxN], c;

int main()
{
    int n,m;
    fin >> n >> m;

    while(m--)
    {
        int x, y, z;
        fin >> x >> y >> z;
        G[x].push_back({y,z});
        G[y].push_back({x,z});
    }

    Q.push({0,1});

    while(!Q.empty())
    {
        int nod = Q.top().second;
        int cost = Q.top().first;
        Q.pop();

        if(viz[nod])
            continue;

        viz[nod] = 1;
        c -= cost;

        for(auto it: G[nod])
            if(!viz[it.first])
                Q.push({-it.second, it.first});
            else if(it.second == -cost)
                rez.push_back({it.first, nod});
    }

    fout << c << "\n";
    fout << rez.size() << "\n";
    for(auto it: rez)
        fout << it.first << " " << it.second << "\n";


    return 0;
}