#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
#define MAXN 200005
#define INF 2e9
struct Edge{
    int v, c;
    Edge(int a, int b){
        v=a, c=b;
    }
};

vector<Edge> G[MAXN];
vector<pair<int,int>> ans;
bool used[MAXN];
int n, m, D[MAXN], parent[MAXN];

int solve(int s){
    int i, choose, total=0;
    for(i=0; i<=n; ++i)
        D[i]=INF, used[i]=0;
    D[s]=0, parent[s]=0;
    for(int pas=1; pas<=n; ++pas){
        choose=0;
        for(i=1; i<=n; ++i)
            if(D[choose]>D[i] && !used[i])
                choose=i;
        used[choose]=1;
        total+=D[choose];
        for(auto e : G[choose])
            if(!used[e.v] && D[e.v] > e.c){
                D[e.v] = e.c;
                parent[e.v]=choose;
            }
    }
    return total;
}

int main(){
    fin>>n>>m;
    int x, y, z;
    while(m--){
        fin>>x>>y>>z;
        G[x].push_back(Edge(y, z));
        G[y].push_back(Edge(x, z));
    }
    cout<<solve(1)<<'\n'<<n-1<<'\n';
    for(int i=2; i<=n; ++i)
        ans.push_back(make_pair(parent[i], i));
    for(auto x : ans)
        fout<<x.first<<" "<<x.second<<'\n';
    return 0;
 }