#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

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

int n, m, i;

int totalCost;

int main()
{

    f>>n>>m;

    vector<list < pair <int ,int> > >adjacencyList(n+1);

    for(i=1; i<=m; i++){

        int x, y, z;
        f>>x>>y>>z;
        adjacencyList[x].push_back(make_pair(y, z));
        adjacencyList[y].push_back(make_pair(x, z));

    }

    set< pair<int, int>>que;

    vector<pair<int, int>>solution(n+1, make_pair(-1, INF));
    vector<int>visited(n+1, false);

    vector<int>dist(n+1, INF);

    que.insert(make_pair(0, 1));
    dist[1] = 0;

    while(!que.empty()){

        pair<int, int> tmp = *(que.begin());
        int u = tmp.second;
        que.erase(que.begin());

        visited[u] = true;

        for(pair<int, int>aux : adjacencyList[u]){

           int v = aux.first;
           int weight = aux.second;

           if(visited[v]==false && dist[v] > weight){

                dist[v] = weight;
                que.insert(make_pair(weight, v));
                solution[v] = make_pair(u, weight);

           }

        }

    }

    for(i=2; i<=n; i++)
        totalCost+=solution[i].second;

    g<<totalCost<<'\n';

    g<<n-1<<'\n';

    for(i=2; i<=n; i++)
        g<<solution[i].first<<' '<<i<<'\n';

    return 0;
}