//Prim
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
const int INF = 1e9;
vector<vector<pair<int,int>>> M;
int d[200001],tata[200001];
bool viz[200001];
void Prim(int n, int s) {
    int cost_total = 0;
    for (int i=1;i<=n;i++) {
        d[i] = INF;
        tata[i] = 0;
    }
    d[s] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>,greater<pair<int,int>>> Q;
    for (int i=1;i<=n;i++)Q.push({d[i], i });
    while (!Q.empty()) {
        int u = Q.top().second; Q.pop();
        if (viz[u])continue;;
        viz[u] = true;
        cost_total+=d[u];
        for ( auto [v, cost] : M[u])
            if (!viz[v] && d[v] > cost) {
                d[v] = cost;
                tata[v] = u;
                Q.push({d[v], v});
            }
    }
    fout<<cost_total<<'\n'<<n-1<<'\n';
    for (int i=1;i<=n;i++)if (s!=i)fout<<tata[i]<<' '<<i<<'\n';

}
int main() {
    int n,m,start;
    fin>>n>>m;
    M.resize(n+1);
    for (int i=1;i<=m;i++) {
        int x,y,cost;
        fin>>x>>y>>cost;
        if (i==1)start = x;
        M[x].push_back({y,cost});
        M[y].push_back({x,cost});
    }

    Prim(n, start);
    return 0;
}


// Conectarea cu cost minim a nodurilor la mai multe surse
// #include <iostream>
// #include <fstream>
// #include <algorithm>
// #include <vector>
// using namespace std;
// ifstream fin ("date.in");
// int tata[10001],h[10001];
// struct muchie{int a,b,cost;};
// bool compara (muchie a, muchie b){return a.cost < b.cost;}
// int reprezentant(int u) {
//     while (tata[u])  u=tata[u];
//     return u;
// }
// void reuniune(int u, int v) {
//     int ru,rv;
//     ru = reprezentant(u);
//     rv = reprezentant(v);
//     if (h[ru] > h[rv]) tata[rv] = ru;
//     else {
//         tata[ru] = rv;
//         if (h[ru] == h[rv]) h[rv]++;
//     }
// }
// int main() {
//     int repetitii;
//     cin>>repetitii;
//     while (repetitii--) {
//         long long int cost_total = 0;
//         int N,S,L,M,counter;
//         vector<muchie> adiacente;
//         vector<int> starts;
//         cin>>N>>M>>L>>S;
//         starts.resize(S);
//         for (int i=1;i<=N;i++) h[i]=tata[i]=0;
//
//         for (int i=0;i<S;i++)cin>>starts[i];
//
//         for (int i=1;i<=M;i++) {
//             int x,y,z;
//             cin>>x>>y>>z;
//             adiacente.push_back({x,y,z});
//         }
//         if (S > 1) for (int i=0;i<S;i++) reuniune(0,i);
//         sort(adiacente.begin(),adiacente.end(),compara);
//
//         for (auto x : adiacente)
//             if (reprezentant(x.a) != reprezentant(x.b)) {
//                 counter++;
//                 cost_total+=x.cost;
//                 reuniune(x.a, x.b);
//                 if (counter == N-S) break;
//             }
//         cost_total += (N-1) * L;
//         cout<<cost_total<<'\n';
//         adiacente.clear();
//     }
//     return 0;
// }

// //cluster
// #include <fstream>
// #include <iostream>
// #include <vector>
// #include <string.h>
// #include <algorithm>
// #include <unordered_set>
// using namespace std;
// ifstream fin ("date.in");
// int dist_lev(char* a, char* b) {
//     int distanta = 0;
//     int lenmic,lenmare;
//     char mic[101],mare[101], aux[101];
//     lenmic = strlen(a); lenmare = strlen(b); //NU E ADEVARAT!!!
//     if(lenmic > lenmare) {
//         strcpy(mare,a);
//         strcpy(mic,b);
//         swap(lenmic,lenmare);
//     }
//     else {
//         strcpy(mare,b);
//         strcpy(mic,a);
//     }
//     for (int i=0;i<lenmic;i++) {
//         char *x = strchr(mare,mic[i]);
//         if (!x) distanta ++;
//         else {
//             strcpy(aux, mare + (x-mare) + 1);
//             strcpy(mare + (x-mare) , aux );
//         }
//     }
//     distanta += lenmare - lenmic;
//     return distanta;
// }
// struct muchie {int a,b,cost;};
// bool compara(muchie a, muchie b){return a.cost <= b.cost;}
// int n,tata[200001],h[200001],counter=0,k=3;
// char x[101],lista[101][101],viz[200001];
// vector<muchie> M;
// unordered_set<int> repr;
// void dfs(int nod) {
//     cout<<lista[nod]<<' ';
//     viz[nod];
//     for (int i=1;i<=n;i++) {
//         if (tata[i] == nod && !viz[i])
//             dfs(i);
//     }
// }
//
// int reprez(int u) {
//     while (tata[u])u = tata[u];
//     return u;
// }
// void reuneste(int u, int v) {
//     int ru,rv;
//     ru = reprez(u);
//     rv = reprez(v);
//     if (h[ru] > h[rv]) {
//         tata[rv] = ru;
//         repr.erase(rv);
//     }
//     else {
//         tata[ru] = rv;
//         repr.erase(ru);
//         if (h[ru] == h[rv]) h[rv]++;
//     }
// }
// int main() {
//     char x[101];
//     while (fin>>x) {
//         n++;
//         strcpy(lista[n],x);
//     }
//
//     for (int i=1;i<=n;i++) {
//         repr.insert(i);
//         for (int j=1;j<=n;j++) {
//             M.push_back({i,j,dist_lev(lista[i], lista[j])});
//         }
//     }
//     sort(M.begin(),M.end(),compara);
//     for (muchie x : M)
//         if (reprez(x.a) != reprez(x.b)) {
//             reuneste(x.a,x.b);
//             counter++;
//             if (counter == n-k) break;
//         }
//     int separare = 100;
//     for (int i=1;i<n;i++)
//         for (int j = i+1; j<=n;j++)
//             if (reprez(i) != reprez(j))
//                 separare = min( separare, dist_lev(lista[reprez(i)], lista[reprez(j)]  ) );
//
//     for (auto i : repr ) {
//         dfs(i);
//         cout<<'\n';
//     }
//     cout<<separare;
//     return 0;
// }

// //kruskal
// #include <iostream>
// #include <fstream>
// #include <vector>
// #include <queue>
// #include <algorithm>
// #include <cmath>
// using namespace std;
// ifstream fin ("date.in");
// ofstream fout ("apm.out");
// struct muchie{
//     int a,b,cost;
// };
// bool compara(muchie a, muchie b) {
//     return a.cost < b.cost;
// }
// vector<muchie> M;
// vector<muchie> tree;
// int n,m,nrnod=0,suma=0;
// int tata[200001], h[200001];
// void init(int u){tata[u] = h[u] = 0;}
// int reprez(int u) {
//     while (tata[u]) u = tata[u];
//     return u;
// }
// void reuneste(int u, int v) {
//     int ru,rv;
//     ru = reprez(u);
//     rv = reprez(v);
//     if (h[ru] > h[rv])
//         tata[rv]=ru;
//     else {
//         tata[ru] = rv;
//         if (h[ru] == h[rv]) h[rv]++;
//     }
// }
// int main() {
//     fin>>n>>m;
//     for (int i=1;i<=m;i++) {
//         int x,y,z;
//         fin>>x>>y>>z;
//         M.push_back({x,y,z});
//         M.push_back({y,x,z});
//     }
//
//     sort(M.begin()+1,M.end(),compara);
//     for ( auto x : M) {
//         if (reprez(x.a) != reprez(x.b)) {
//             tree.push_back(x);
//             reuneste(x.a, x.b);
//             nrnod++;
//             suma+=x.cost;
//             if (nrnod == n-1)
//                 break;
//         }
//     }
//     cout<<suma<<'\n'<<nrnod<<'\n';
//     for (int i=0;i<nrnod;i++)
//         cout<<tree[i].b<<' '<<tree[i].a<<'\n';
//     return 0;
// }