#include <fstream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

vector<pair<int,int>> G[200005];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int dist[200005], t[200005], vis[200005];

int prim(int n, int s)
{
    int res = 0;
    for(int i=1;i<=n;i++)
        dist[i] = INT_MAX;
    dist[s] = 0;
    pq.push(make_pair(0,s));

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

        if(vis[nod])
            continue;
        vis[nod] = 1;
        res += cost;

        for(auto x : G[nod])
        {
            int vecin = x.second;
            int c2 = x.first;
            if(!vis[vecin] && c2 < dist[vecin])
            {
                dist[vecin] = c2;
                t[vecin] = nod;
                pq.push(make_pair(c2, vecin));
            }
        }
    }

    return res;
}

int main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");

    int n, m, x, y, c, res;
    cin >> n >> m;
    for(int i=0;i<m;i++)
    {
        cin >> x >> y >> c;
        G[x].push_back(make_pair(c,y));
        G[y].push_back(make_pair(c,x));
    }

    res = prim(n, 1);

    cout << res << '\n' << n-1 << '\n';

    for(int i=2;i<=n;i++)
    {
        cout << i << " " << t[i] << '\n';
    }
    return 0;
}