#include <fstream>
#include <vector>
#include <set>

using namespace std;

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


const int N = 2e5, INF = 3e8;
int n, m, cost_tot;
int d[N+1], from[N+1];
bool viz[N+1];
vector < pair<int , int> > g[N+1], ans;
set < pair<int, int> > s;


void prim()
{
    for (int i = 1; i <= n; i++)
        d[i] = INF;
    d[1] = 0;
    from[1] = 1;

    for (int i = 1; i <= n; i++)
        s.insert( make_pair(d[i], i) );
    
    for (int i = 1; i <= n; i++)
    {
        int curr_node = s.begin()->second, cost = s.begin()->first;
        s.erase(s.begin());
        viz[curr_node] = true;
        cost_tot += cost;
        if (from[curr_node] != curr_node)
            ans.push_back( make_pair(curr_node, from[curr_node]) );

        for (auto it : g[curr_node])
        {
            int vec = it.first, c = it.second;
            if (viz[vec] == false && c < d[vec])
            {
                s.erase( make_pair(d[vec], vec) );
                d[vec] = c, from[vec] = curr_node;
                s.insert( make_pair(d[vec], vec) );
            }
        }
    }
}


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

    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back( make_pair(b, c) );
        g[b].push_back( make_pair(a, c) );
    }


    prim();

    cout << cost_tot << '\n';
    cout << ans.size() << '\n';
    for (auto pereche : ans)
        cout << pereche.first << ' ' << pereche.second << '\n';


    return 0;
}