#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
#include <climits>
using namespace std;


int p[100001];
int h[100001];

int Find(int x){
    while (x!=p[x]){
        x=p[x];
    }

    return x;
}

void Union(int x, int y){
    x=Find(x);
    y=Find(y);

    if(h[x]<h[y]){
        p[x]=y;
    }
    else{
        if(h[x]>h[y]){
            p[y]=x;
        }
        else{
            p[x]=y;
            h[y]++;
        }
    }
}

bool comparePairs(const pair<pair<int, int>, int>& a, const pair<pair<int, int>, int>& b) {
return a.second < b.second;
}


vector <pair<pair<int,int>,int>> muchii;

vector <pair<int,int>> solutie;
//Kruskal

// int main(){

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

//     int n;
//     cin>>n;
//     int m;
//     cin>>m;

//     for(int i=1; i<=n; i++){
//         p[i]=i;
//         h[i]=0;
//     }

//     for(int i=0; i<m; i++){
//         int x,y,c;
//         cin>>x>>y>>c;
//         muchii.push_back(make_pair(make_pair(x,y),c));
//     }

//     sort(muchii.begin(), muchii.end(), comparePairs);

//     int sol=0;

//     for(const auto& e : muchii){
//         if (Find(e.first.first) != Find(e.first.second)) {
//             sol+=e.second;
//             solutie.push_back(e.first);
//             Union(e.first.first, e.first.second);
//         }
//     }

//     cout<<sol<<'\n';
//     cout<<solutie.size()<<'\n';
//     for(const auto& i : solutie){
//         cout<<i.first<<" "<<i.second<<'\n';
//     }


//     return 0;
// }

int viz[100001];
int parent[100001];
vector<pair<int, pair<int, int>>> adj[100001];

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

    int n;
    cin>>n;
    int m;
    cin>>m;

    for(int i=0; i<m; i++){
        int x,y,c;
        cin>>x>>y>>c;
        adj[x].push_back({c, {x, y}});
        adj[y].push_back({c, {y, x}});
    }
    
    if(n == 0){
        cout << 0 << '\n' << 0 << '\n';
        return 0;
    }

    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
    
    int sol = 0;
    vector<pair<int, int>> mst_edges;
    
    int start = 1;
    viz[start] = 1;
    
    for(const auto& edge : adj[start]){
        int cost = edge.first;
        int u = edge.second.first;
        int v = edge.second.second;
        pq.push({cost, {u, v}});
    }

    while(!pq.empty()){
        auto cur = pq.top();
        pq.pop();
        
        int cost = cur.first;
        int u = cur.second.first;
        int v = cur.second.second;
        
        if(viz[v]){
            continue;
        }
        
        viz[v] = 1;
        sol += cost;
        mst_edges.push_back({u, v});
        
        for(const auto& edge : adj[v]){
            int new_cost = edge.first;
            int new_u = edge.second.first;
            int new_v = edge.second.second;
            
            if(!viz[new_v]){
                pq.push({new_cost, {new_u, new_v}});
            }
        }
    }

    cout << sol << '\n';
    cout << mst_edges.size() << '\n';
    for(const auto& edge : mst_edges){
        cout << edge.first << " " << edge.second << '\n';
    }

    return 0;
}