#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

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

auto cmp = [](pair<int,int> a, pair<int,int>b)
{
    return a.second > b.second;
};
priority_queue <pair<int,int>, vector <pair<int,int>>,decltype(cmp)> pq(cmp);
int n,m,a,b,i,pret,total_cost,cost[200001],tata[200001];
bitset <200001> trecut;
vector <pair<int,int>> v[2000001];

int main()
{
    ios::sync_with_stdio(0);
    f >> n >> m;
    while(m --)
    {
        f >> a >> b >> pret;
        v[a].push_back({b,pret});
        v[b].push_back({a,pret});
    }
    for(i = 1; i <= n; ++ i)
        cost[i] = INF;
    for(i = 0; i < v[1].size(); ++ i)
    {
        a = v[1][i].first;
        b = v[1][i].second;
        cost[a] = b;
        tata[a] = 1;
        pq.push({a,b});
    }
    trecut[1] = 1;
    cost[1] = 0;
    while(!pq.empty())
    {
        a = pq.top().first;
        pq.pop();
        trecut[a] = 1;
        for(i = 0; i < v[a].size(); ++ i)
            if(!trecut[v[a][i].first] && cost[v[a][i].first] > v[a][i].second)
            {
                cost[v[a][i].first] = v[a][i].second;
                tata[v[a][i].first] = a;
                pq.push({v[a][i].first,v[a][i].second});
            }
    }
    for(i = 1; i <= n; ++ i)
        total_cost += cost[i];
    g << total_cost << '\n' << n - 1 << '\n';
    for(i = 2; i <= n; ++ i)
        g << i << ' ' << tata[i] << '\n';
}