#include <bits/stdc++.h>
#define NMAX 200005
#define INF 0x3f3f3f3f

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n, m, drum[NMAX];
int parent[NMAX];
bitset <NMAX> v;
vector <pair <int, int>> edges[NMAX];
set <pair <int, int>> s;

int main()
{
    f >> n >> m;

    for(int i = 1; i <= n; i++)
        drum[i] = INF;

    for(int i = 1; i <= m; i++)
    {
        int x, y, cost;
        f >> x >> y >> cost;
        edges[x].push_back(make_pair(y, cost));
        edges[y].push_back(make_pair(x, cost));
    }

    drum[1] = 0;
    s.insert({0, 1});
    while(!s.empty())
    {
        int nod = s.begin() -> second;
        s.erase(s.begin());

        if(v[nod] == 1)
            continue;

        v[nod] = 1;

        for(auto k : edges[nod])
            if(!v[k.first] && drum[k.first] > k.second)
            {
                s.erase(make_pair(drum[k.first], k.first));
                drum[k.first] = k.second;
                parent[k.first] = nod;
                s.insert(make_pair(drum[k.first], k.first));
            }
    }

    int cost = 0;

    for(int i = 1; i <= n; i++)
        cost += drum[i];

    g << cost << "\n" << n - 1 << "\n";
    for(int i = 2; i <= n; i++)
        g << parent[i] << " " << i << "\n";


    return 0;
}