#include <bits/stdc++.h>
using namespace std;
ifstream in ("apm.in");
ofstream out ("apm.out");
vector <pair <int , int> > v[200001];
int dist[200001], tata[200001];
bool viz[200001];
void solve ()
{
    int n,m;
    in >> n >> m;
    for (int i = 1;i<=n;++i)
        dist[i] = INT_MAX;
    for (int i = 1;i<=m;++i)
    {
        int a, b, c;
        in >> a >> b >> c;
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }
    set <pair <int, int> > seti;
    // set {place,cost};
    seti.insert({0, 1});
    dist[1] = 0;
    while (!seti.empty())
    {
        int place = (*seti.begin()).second;
        seti.erase(seti.begin());
        viz[place] = 1;
        for (auto nod: v[place])
        {
            if (!viz[nod.first] && dist[nod.first] > nod.second)
            {
               seti.insert({nod.second, nod.first});
               dist[nod.first] = nod.second;
               tata[nod.first] = place;
            }
        }
    }
    int rez = 0;
    for (int i = 1;i<=n;++i)
        rez += dist[i];
    out << rez << '\n' << n - 1 << '\n';
    for(int i = 2;i<=n;++i)
        out << i << ' ' << tata[i] << '\n';
    return;
}
int main ()
{
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
}