#include <bits/stdc++.h>

using namespace std;

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

typedef pair<int,pair<int,int>> piii;

const int nmax=105;

priority_queue <piii,vector<piii>,greater<piii>> q;
vector <piii> g[nmax], sol;
int n, m, cost, sel[nmax];

void prim (int node)
{
    for (int i=1; i<=n; i++)
        sel[i]=false;
    cost=0;
    sel[node]=true;
    for (auto i:g[node])
        q.push(i);
    while (!q.empty())
    {
        int c=q.top().first;
        int k=q.top().second.second;
        if (sel[k])
        {
            q.pop();
            continue;
        }
        sel[k]=true;
        cost+=c;
        sol.push_back(q.top());
        q.pop();
        for (auto i:g[k])
            q.push(i);
    }
}

int main()
{
    fin >> n >> m;
    for (int i=1; i<=m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        g[x].push_back({c,{x,y}});
    }
    prim(1);
    fout << cost << '\n' << sol.size() << '\n';
    for (auto i:sol)
        fout << i.second.first << " " << i.second.second << '\n';
}