#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std ;

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

const int inf = 0x3f3f3f3f;
const int NMAX = 200001;

int n, m; ;
vector <pair<int,int>>  G[NMAX] ;
vector <int> Dist, Parent, Viz;
int ans;

int main ()
{
    f >> n >> m ;
    for (int i = 1; i <= m; ++i)
    {
        int a, b, c;
        f >> a >> b >> c;
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }
    Dist = vector <int> (n + 1, inf);
    Parent = vector <int> (n + 1, -1);
    Viz = vector <int> (n + 1);
    priority_queue <pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> Q;
    Parent[1] = 0;
    Dist[1] = 0;
    Q.push({Dist[1], 1});
    while (!Q.empty())
    {
        int x = Q.top().second, dx = Q.top().first;
        Q.pop();
        Viz[x] = 1;
        for (const pair<int,int> p : G[x])
        {
            int y = p.first, w = p.second;
            if (Dist[y] > w && Viz[y] == false)
            {
                Dist[y] = w;
                Parent[y] = x;
                Q.push({Dist[y], y});
            }
        }
    }
    for (int i = 1; i <= n; ++i)
        ans += Dist[i];
    g << ans << "\n" << n - 1 << "\n";
    for (int i = 1; i <= n; ++i)
        if (Parent[i])
            g << Parent[i] << " " << i << "\n";
    return 0;
}