#include  <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
const int NMAX = 1e5;


struct Edge {
    int u,v,w;
    bool operator<( const Edge &m) const{
        return w<m.w;
    }
};

vector<Edge> apm,edg;

int find(int x, vector<int> &v) {
    if (v[x]==0)
        return x;
    return find( v[x], v) ;
}

void unire ( int x, int y, vector< int> &tata , vector<int> &rang) {
    int rx= find( x, tata);
    int ry= find(y,tata);

    if ( rang[rx] < rang [ry]) swap (rx, ry);
    tata[ry]=rx;
    if ( rang[rx] == rang[ry]) rang[rx]++ ;
}



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

int main () {

    // HAVEL HAKIMI -
    //
    //global
    //
    //// bool havelHakimi(int deg[NMAX+1], int m) {
    //
    //     int sum=0;
    //     for (int i=0; i<m; i++) {
    //         sum+=deg[i];
    //         if (deg[i]>=m) return false;
    //         if (deg[i]<0) return false;
    //     }
    //     if ( sum%2 ==1 ) return false;
    //     sort(deg, deg+m, greater<int>());
    //     for (int i=0; i<m; i++) {
    //         int t=deg[i];
    //         if (t > m-i-1) return false;
    //         for (int j=i+1; j<i+t+1; j++) {
    //             deg[j]--;
    //             if (deg[j]<0) return false;
    //         }
    //         deg[i]=0;
    //         if (deg[i]>0 ) return false;
    //         sort(deg, deg+m, greater<int>());
    //     }
    //     return true;
    // }
    //
    //main
    //
    // int n, m;
    // in>>n;
    // for (int i=0; i<n; i++) {
    //     in>>m;
    //     int deg[100001];
    //     for (int j=0; j<m; j++) {
    //         in>>deg[j];
    //     }
    //     int ok=havelHakimi(deg, m);
    //
    //     if (ok==1) out<<"POSSIBLE"<<endl;
    //     else out<<"IMPOSSIBLE"<<endl;
    // }


    //BFS - distanta de la un nod S la restul nodurilor
    // int n,m,a,b,s;
    // in>>n>>m>>s;
    // vector<vector<int> > adj(n+1);
    //
    // for (int i=0; i<m; i++) {
    //     in>>a>>b;
    //     adj[a].push_back(b);
    // }
    // vector<int> dist(n+1, -1);
    // queue<int> q;
    // dist[s]=0;
    // q.push(s);
    //
    // while(!q.empty()) {
    //     int u=q.front();
    //     q.pop();
    //     for ( auto i : adj[u]) {
    //         if (dist[i]==-1) {
    //             dist[i]=dist[u]+1;
    //             q.push(i);
    //         }
    //     }
    // }
    //
    // for ( int i=1; i<=n; i++ ) {
    //     out<<dist[i]<<" ";
    // }

    //DFS - cate componente conexe are un graf
    // int n,m;
    // in>>n>>m;
    // vector<vector<int>> lista(1000000);
    // for ( int i=1;i<=m;i++) {
    //     int x,y;
    //     in>>x>>y;
    //     lista[x].push_back(y);
    //     lista[y].push_back(x);
    // }
    //
    // vector< int> vis(n+1, 0);
    // vector<int> stack;
    // int comp=0;
    //
    // for (int i=1;i<=n;i++) {
    //     if (!vis[i]) {
    //         comp++;
    //         stack.clear();
    //         stack.push_back(i);
    //         vis[i]=1;
    //     }
    //     else continue;
    //     while (!stack.empty()) {
    //         int u=stack.back();
    //         stack.pop_back();
    //         for ( auto v : lista[u]) {
    //             if ( !vis[v] ) {
    //                 vis[v]=1;
    //                 stack.push_back(v);
    //             }
    //         }
    //     }
    // }
    //
    // out << comp << endl;

    //BFS - berarie2 muchii inversate
    // int n,m,p;
    // in>>n>>m>>p;
    // vector<vector<int> > adj (n+1);
    // for ( int i = 1; i <= m; i++ ) {
    //     int x,y;
    //     in>>x>>y;
    //     adj[y].push_back(x);
    // }
    // queue<int> q;
    // vector<int> vis (n+1,0);
    //
    // for (int i = 1; i <= p; i++ ) {
    //     int z;
    //     in>>z;
    //     if (!vis[z]) {
    //         vis[z] = 1;
    //         q.push(z);
    //     }
    // }
    //
    // while ( !q.empty() ) {
    //     int x = q.front();
    //     q.pop();
    //     for ( auto v: adj[x] ) {
    //         if ( !vis[v] ) {
    //             vis[v] = 1;
    //             q.push(v);
    //         }
    //     }
    // }
    // vector<int> ans;
    // for ( int i = 1; i <= n; i++ ) {
    //     if ( !vis[i] ) {
    //         ans.push_back(i);
    //     }
    // }
    // out<<ans.size()<<endl;
    // for ( int i = 0; i < ans.size(); i++ ) {
    //     out<<ans[i]<<"\n";
    // }


    // KOSARAJU - determina ctc dintr-un graf
    //
    // asta e in global
    //
    // vector<vector<int>> g;
    // vector<vector<int>> gT;
    // vector<int> viz;
    // stack<int> st;
    //
    // void dfs(int vf){
    //     viz[vf]=1;
    //     for (int x: g[vf]) {
    //         if (!viz[x])
    //             dfs(x);
    //
    //     }
    //     st.push(vf);
    // }
    //
    // void dfsT(int vf, vector<int> &v) {
    //     viz[vf]=1;
    //     v.push_back(vf);
    //     for ( int x : gT[vf]) {
    //         if (!viz[x])
    //             dfsT(x,v);
    //     }
    // }
    //
    // asta e in main
    //
    // int n,m;
    // in>>n>>m;
    // g.resize(n+1);
    // gT.resize(n+1);
    // viz.assign(n+1, 0);
    // for( int i=1;i<=m;i++) {
    //     int x,y;
    //     in>>x>>y;
    //     g[x].push_back(y);
    //     gT[y].push_back(x);
    // }
    //
    // for ( int i=1;i<=n;i++) {
    //     if (!viz[i])
    //         dfs(i);
    // }
    // viz.assign(n+1,0);
    // vector<vector<int>> comp;
    //
    // while (!st.empty()) {
    //     int vf = st.top();
    //     st.pop();
    //     if ( !viz[vf]) {
    //         vector<int> vv;
    //         dfsT(vf,vv);
    //         comp.push_back(vv);
    //     }
    // }
    //
    // out<<comp.size()<<endl;
    // for (vector<int> v : comp) {
    //     for (int x: v) {
    //         out<< x<< " ";
    //     }
    //     out<< endl;
    // }


    //SORTARE TOPOLOGICA

    // global
    // vector<vector<int>> adj;
    // vector<int> viz, ord;
    //
    // void dfs(int vf) {
    //     viz[vf]=1;
    //     for ( auto x : adj[vf]) {
    //         if (!viz[x])
    //             dfs(x);
    //     }
    //     ord.push_back(vf);
    // }
    //
    // main
    // int n,m;
    // in>>n>>m;
    // viz.resize(n+1);
    // adj.resize(n+1);
    // ord.clear();
    // for (int i=1;i<=m;i++) {
    //     int x,y;
    //     in>>x>>y;
    //     adj[x].push_back(y);
    // }
    //  for ( int i =1; i<=n; i++) {
    //      if (!viz[i])
    //          dfs(i);
    //  }
    //
    // reverse(ord.begin(), ord.end());
    //
    // for ( int i : ord) out<< i<< " ";


    //bipartit -colorare bfs mod
    // int n,m;
    // in>>n>>m;
    // vector<vector<int> > adj(n+1);
    // vector<int> color( n+1, 0);
    // queue<int> q;
    //
    // for ( int i=1;i<=m;i++) {
    //     int x,y;
    //     in>>x>>y;
    //     adj[x].push_back(y);
    //     adj[y].push_back(x);
    // }
    //
    // for (int i=1;i<=n;i++) {
    //     if (color[i]==0 ) {
    //         color[i]=1;
    //         q.push(i);
    //
    //         while (!q.empty()) {
    //             int u=q.front();
    //             q.pop();
    //             for ( int x : adj[u]) {
    //                 if ( color[x] == 0) {
    //                     color[x]=3-color[u];
    //                     q.push(x);
    //                 }
    //                 else if (color[x]==color[u]) {
    //                     out<<"IMPOSSIBLE\n";
    //                     return 0;
    //                 }
    //             }
    //         }
    //     }
    // }
    // for ( int i =1; i<=n;i++)
    //     out<< color[i]<< " ";

    // Tarjan - puncte de articulatie problema Vice City
    //
    //global
    //
    // vector<int> lista[NMAX+1];
    // vector<bool> rez;
    // int tin[NMAX+1], low[NMAX+1], timer;
    //
    // void dfs(int u, int parent) {
    //     int children=0;
    //     tin[u]= low[u]= ++timer;
    //     for ( int v: lista[u]) {
    //         if (v ==parent) continue;
    //         if (tin[v]== 0) {
    //             children++;
    //             dfs(v, u);
    //             low[u]=min(low[u],low[v]);
    //             if ( parent != -1  && low[v]>=tin[u])
    //                 rez[u]= true;;
    //         }
    //         else{
    //             low[u]=min(low[u],tin[v]);
    //         }
    //     }
    //     if ( parent == -1 && children >=2 )
    //         rez[u]=true;
    // }
    //
    //main
    // int n,m;
    // cin>>n>>m;
    // while ( n!=0 && m!=0 ) {
    //
    //     for( int i =0 ; i<= n; i++)  lista[i].clear();
    //     timer=0;
    //     for( int i =0 ; i<= n; i++)  tin[i]=low[i]=0;
    //     rez.assign(n+1, false);
    //
    //     for ( int i=1;i<=m;i++) {
    //         int a,b;
    //         cin>>a>>b;
    //         lista[a].push_back(b);
    //         lista[b].push_back(a);
    //     }
    //
    //     for ( int i =1; i<=n;i++) {
    //         if ( tin[i]==0)
    //             dfs(i,-1);
    //     }
    //     int ans=0;
    //     for (int i=1;i<=n;i++) {
    //         if (rez[i]) ans++;
    //     }
    //     cout<< ans<< '\n';
    //     cin>>n>>m;
    // }
    //


    //KRUSKAL

    int n,m,cost=0;
    in>>n>>m;
    for ( int i=1; i<=m;i++) {
        Edge e;
        in>>e.u>>e.v>> e.w;
        edg.push_back(e);
    }

    sort(edg.begin(), edg.end());

    vector<int> tata(n+1,0), rang(n+1,0);
    for ( auto &e: edg) {
        if ( apm.size() == n-1 )
            break;
        if ( find(e.u, tata)!= find( e.v,tata)) {
            cost+=e.w;
            apm.push_back(e);
            unire(e.u,e.v,tata, rang);
        }
    }

    out<< cost<< '\n';
    out<<apm.size()<<'\n';

    for ( auto &e: apm) {
        out<<e.u<<" "<<e.v<<'\n';
    }

    return 0;
}