#include <bits/stdc++.h>
#define pii pair<int,int>
#define piii pair< int , pii>
using namespace std;

const int NMAX = 2e5 + 5;

int n , m , u , v , c , node , nxt , f[NMAX] , ans_cost;
vector <pii> g[NMAX] , ans;
priority_queue <piii , vector <piii> , greater <piii> > Q;
piii p;
int main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");

    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {

        cin >> u >> v >> c;
        g[u].push_back({v , c});
        g[v].push_back({u , c});

    }

    Q.push({0 , {0 , 1} });
    while(!Q.empty())
    {

        p = Q.top();
        Q.pop();

        node = p.second.second;

        if(f[node])continue;
        ans.push_back({p.second.first , node});
        f[node] = 1;

        ans_cost += p.first;
        for(int i = 0; i < g[node].size(); i++)
            Q.push({g[node][i].second , {node , g[node][i].first} });
    }

    cout << ans_cost << "\n";
    cout << ans.size() - 1 << "\n";
    for(int i = 1; i < ans.size(); i++)
        cout << ans[i].first << " " << ans[i].second << "\n";
    return 0;
}