#include <bits/stdc++.h>
/// WARNING : IMPLEMENTAREA MEA DUPA CE AM VAZUT UN VIDEO DE 2 MINUTE DESPRE ALGORITMUL LUI PRIM, NUSH DK E BINE
using namespace std;

#define Read_Optimizations ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define FOR(n) for(int i = 1; i <= n; ++ i)
#define REP(i, n) for(int idx = i; idx <= n; ++ idx)
//#define int long long
#define pb push_back
#define pii pair<int, int>
using ll = long long;
using ci = const int;
using cll = const long long;

/// INPUT / OUTPUT
const string problem = "apm";
ifstream fin(problem + ".in");
ofstream fout(problem + ".out");
/////////////////////////////////////////////////////////////////////

/// STRUCTURES
struct priority
{
    int x, y, cost;

    bool operator < (const priority &num) const
    {
        return cost > num.cost;
    }
};
/////////////////////////////////////////////////////////////////////

/// GLOBAL VARIABLES
const int NMAX = 2e5 + 5, MMAX = 4e5+5;
int N, M;
int ans, edge_num;
bool viz[NMAX];
int min_cost[NMAX];
vector<pii>mst;
vector<pii>graph[NMAX];
/////////////////////////////////////////////////////////////////////

/// FUNCTIONS
inline void Prim(int node)
{
    priority_queue<priority>pq;
    pq.push({node, 0, 0});
    viz[node] = 1;

    while(!pq.empty())
    {
        int curr_node = pq.top().x;
        int sec_node = pq.top().y;
        int curr_cost = pq.top().cost;
        pq.pop();

        if(!viz[curr_node] && curr_node != 1)
        {
            mst.push_back({curr_node, sec_node});
            ans += curr_cost;
            edge_num++;
            viz[curr_node] = 1;
        }
        else if(viz[curr_node] && curr_node != 1) continue;

        for(auto new_node : graph[curr_node])
        {
            if(!viz[new_node.first])
            {
                pq.push({new_node.first, curr_node, new_node.second});
            }
        }
    }
}

inline void debugGraph()
{
    for(int i = 1; i <= N; ++ i)
    {
        cout << i << ": ";

        for(auto x : graph[i])
        {
            cout << x.first << ',' << x.second << "   ";
        }
        cout << '\n';
    }
}
/////////////////////////////////////////////////////////////////////

/// SOLUTION
int main()
{
    Read_Optimizations

    fin >> N >> M;

    while(M--)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        graph[x].push_back({y, cost});
        graph[y].push_back({x, cost});
    }

    Prim(1);

    fout << ans << '\n' << edge_num << '\n';

    for(auto x : mst)
        fout << x.first << ' ' << x.second << '\n';
}