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

using namespace std ;
ifstream lol("apm.in");
ofstream lmao("apm.out") ;

vector <pair<int,int>> L[200001];
int d[200001], p[200001], vis[200001];

int main() {
    int n,m;
    lol>>n>>m;
    for(int i=1; i<=m; ++i) {
        int x,y,c;
        lol>>x>>y>>c;
        L[x].push_back({y,c}) ;
        L[y].push_back({x,c});
    }
    for(int i=1;i<=n; ++i) {
        d[i] =1e9;
    }
    d[1] = 0;
    int sum =  0;
    priority_queue<pair<int,int>> pq ; // d[nod[, nod]]
    pq.push({d[1],1}) ;
    while(pq.empty() == false) {
        // int nod = 0; 
        // int minim = 1e9;
        // for(int j= 1 ;j<=n; ++j) {
        //     if(vis[j] == 0 && d[j] < minim) {
        //         minim = d[j];
        //          nod = j;
        //     }
        // }

        int nod = pq.top().second;
        pq.pop();
        if(vis[nod] == 1) {
            continue;
        }
        sum += d[nod] ;
        vis[nod] = 1 ;
        for(auto it : L[nod]) {
            int vec = it.first ;
            int cost = it.second ;
            if(vis[vec] == 0 && d[vec] > cost) {
                d[vec] = cost ;
                p[vec] = nod ;
                pq.push({-d[vec],vec}) ;
            }
        }
    }
    lmao << sum << "\n";
    lmao << n - 1 << "\n";
    for(int i = 2; i <= n; ++i) {
        lmao << i << " " << p[i] << "\n";
    }


    return 0;
}