// #include <bits/stdc++.h>
//
// using namespace std;
// int a[101][101], viz[101], nod_sos, cnt=0,ok=0, nivel[101];
// vector<int> v;
// queue<int> q;
// int n;
//
// void dfs(int nod) {
//     cout<<nod<<" ";
//     viz[nod]=1;
//     for (int i=1;i<=n;i++) {
//         if (viz[i]==0 and a[nod][i]==1 and a[i][nod]==1)
//             dfs(i);
//     }
// }
//
// int main() {
//     int m, nod_plecare, x, y;
//     cin >> n >> m >> nod_plecare >> nod_sos;
//     for (int i=1; i<=m; i++) {
//         cin>>x>>y;
//         a[x][y]=1;
//     }
//     for (int i=1;i<=n;i++) {
//         if (!viz[i])
//             dfs(i);
//         cout<<endl;
//     }
//     return 0;
// }

// Sortare topologica BFS

// #include <bits/stdc++.h>
//
// using namespace std;
// int a[101][101], viz[101];
// int f[101];
// vector<int> v;
// queue<int> q;
// int n;
//
// void bfs(int nod) {
//     while (!q.empty()) {
//         int k = q.front();
//         q.pop();
//         for (int i=1;i<=n;i++) {
//             if (a[k][i]==1) {
//                 f[i]--;
//             }
//             if (f[i]==0 and a[k][i]==1) {
//                 q.push(i);
//                 v.push_back(i);
//             }
//         }
//     }
//     if (v.size()==n){
//         for (int i=0;i<v.size();i++) {
//             cout<<v[i]<<" ";
//         }
//     }
// }
//
// int main() {
//     int m, x, y;
//     cin >> n >> m;
//     for (int i=1; i<=m; i++) {
//         cin>>x>>y;
//         a[x][y]=1;
//         f[y]++;
//     }
//     for (int i=1;i<=n;i++) {
//         if (f[i]==0) {
//             q.push(i);
//             v.push_back(i);
//         }
//     }
//     for (int i=1;i<=n;i++) {
//         if (f[i]==0) {
//             bfs(i);
//             break;
//         }
//     }
//     return 0;
// }

// Algoritm muchii critice

// #include <bits/stdc++.h>
//
// using namespace std;
// int a[101][101],viz[101],n,nivel[101], niv_min[101];
// set<int> vecini[100];
//
// void dfs(int nod) {
//     viz[nod]=1;
//     niv_min[nod]=nivel[nod];
//     for (auto y : vecini[nod]) {
//         if (viz[y]==0) {
//             nivel[y]=nivel[nod]+1;
//             dfs(y);
//
//             niv_min[nod]=min(niv_min[nod],niv_min[y]);
//
//             if (niv_min[y] > nivel[nod])
//                 cout<<nod<<" "<<y<<endl;
//         }
//         else {
//             if (nivel[y] < nivel[nod] - 1) {
//                 niv_min[nod]=min(niv_min[nod],nivel[y]);
//             }
//         }
//     }
// }
//
// int main() {
//     int n,m,x,y;
//     cin>>n>>m;
//     for (int i=1;i<=m;i++) {
//         cin>>x>>y;
//         vecini[x].insert(y);
//         vecini[y].insert(x);
//     }
//     dfs(1);
//
// }

// Alg Pct. critice

// #include <bits/stdc++.h>
//
// using namespace std;
// int a[101][101],viz[101],n,nivel[101], niv_min[101];
// set<int> vecini[100];
//
// void dfs(int nod) {
//     viz[nod]=1;
//     niv_min[nod]=nivel[nod];
//     for (auto y : vecini[nod]) {
//         if (viz[y]==0) {
//             nivel[y]=nivel[nod]+1;
//             dfs(y);
//
//             niv_min[nod]=min(niv_min[nod],niv_min[y]);
//
//             if (niv_min[y] >= nivel[nod])
//                 cout<<nod<<" ";
//         }
//         else {
//             if (nivel[y] < nivel[nod] - 1) {
//                 niv_min[nod]=min(niv_min[nod],nivel[y]);
//             }
//         }
//     }
// }
//
// int main() {
//     int n,m,x,y;
//     cin>>n>>m;
//     for (int i=1;i<=m;i++) {
//         cin>>x>>y;
//         vecini[x].insert(y);
//         vecini[y].insert(x);
//     }
//     dfs(1);
//
// }

// Alg. Kosaraju

// #include <bits/stdc++.h>
//
// using namespace std;
// vector <int> v;
// int n,a[101][101],viz[101],a1[101][101];
// int viz2[101];
// set<int> s;
//
// void dfs(int nod) {
//     viz[nod]=1;
//     v.push_back(nod);
//     for (int i=1;i<=n;i++) {
//         if (a[nod][i]==1 and viz[i]==0)
//             dfs(i);
//     }
// }
//
// void dfs2(int nod) {
//     viz2[nod]=1;
//     cout<<nod<<" ";
//     for (int i=1;i<=n;i++) {
//         if (a1[nod][i]==1 and viz2[i]==0) {
//             dfs2(i);
//         }
//     }
// }
//
// int main() {
//     int m,x,y;
//     cin>>n>>m;
//     for(int i=1;i<=m;i++) {
//         cin>>x>>y;
//         a[x][y]=1;
//         a1[y][x]=1;
//     }
//     for (int i=1;i<=n;i++) {
//         if (viz[i]==0) {
//             dfs(i);
//         }
//     }
//     for (int i=0; i<v.size(); i++) {
//         if (viz2[v[i]]==0) {
//             dfs2(v[i]);
//         }
//         cout<<endl;
//     }
//     return 0;
// }

#include <bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
set<pair<int, int>> vecini[100];
int n,m,x,y,c,a[101][101],d[101], tata[101], viz[101];
const int INF = 1e9;

void prim(int nod) {
    for (int i=1;i<=n;i++) {
        d[i]=INF;
        tata[i]=0;
    }
    d[nod] = 0;
    pq.push(make_pair(0,nod));

    int luate = 0;
    long long cost_total = 0;

    while (!pq.empty() and luate < n) {
        int u = pq.top().second;
        int cost = pq.top().first;
        pq.pop();

        if (viz[u]) continue;
        if (cost != d[u]) continue;

        viz[u] = 1;
        luate++;
        cost_total += cost;

        for (auto it : vecini[u]) {
            int v = it.first;
            int w = it.second;
            if (!viz[v] && w < d[v]) {
                d[v] = w;
                tata[v] = u;
                pq.push(make_pair(w,v));
            }
        }
    }
    for (int i=1; i<=n ;i++) {
        if (d[i] == INF) {
            fout<<"Graful nu este conex";
            return;
        }
    }
    fout<<cost_total<<endl;
    int cnt=0;
    for (int i=1; i<=n; i++) {
        if (i!=nod)
            cnt++;
    }
    fout<<cnt<<endl;
    for (int i=1; i<=n; i++) {
        if (i!=nod)
            fout<<tata[i]<<" "<<i<<endl;
    }
}

int main() {
    fin>>n>>m;
    for (int i=1;i<=m;i++) {
        fin>>x>>y>>c;
        vecini[x].insert({y, c});
        vecini[y].insert({x, c});
    }
    prim(1);
    return 0;
}