#include <bits/stdc++.h>

using namespace std;

#if 1
    #define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
    #define pn cout<<endl
#else
    #define pv(x)
    #define pn
#endif

#ifdef ONLINE_JUDGE
    #define in cin
    #define out cout
#else
    ifstream in("apm.in");
    ofstream out("apm.out");
#endif

using ll = long long;
using ull = unsigned long long;
using ui = unsigned int;
#define pb push_back
#define mp make_pair
const int NMax = 4e5 + 5;
const ll inf_ll = 1e18 + 5;
const int inf_int = 1e9 + 5;
const int mod = 100003;
using zint = int;

int N,M;
int lung[NMax];
bool inAPM[NMax];

struct elem {
    int x,y,c;
    elem(int _x = 0,int _y = 0,int _c = 0) {
        x = _x;
        y = _y;
        c = _c;
    }
};
vector<elem> sol,v[NMax];

bool operator<(elem a,elem b) {
    if (a.c == b.c) {
        if (a.x == b.x) {
            return a.y < b.y;
        }
        return a.x < b.x;
    }
    return a.c < b.c;
}

int main() {
    in >> N >> M;
    for (int i = 1;i <= M;++i) {
        int x,y,c;
        in >> x >> y >> c;

        v[x].pb( {x,y,c} );
        v[y].pb( {y,x,c} );
    }

    for (int i = 1;i <= N;++i) {
        lung[i] = inf_int;
    }
    lung[1] = 0;
    inAPM[1] = true;

    set<elem> st;
    st.insert(elem(0,1,0));
    ll costAPM = 0;
    while (st.size()) {
        auto top = *st.begin();
        st.erase(st.begin());

        int dad = top.x, node = top.y, costMuchie = top.c;
        if (lung[node] < costMuchie) {
            continue;
        }
        inAPM[node] = true;

        costAPM += costMuchie;
        sol.pb( top );
        for (auto p : v[node]) {
            int nxt = p.y, cost = p.c;
            if (lung[nxt] <= cost || inAPM[nxt]) {
                continue;
            }

            lung[nxt] = cost;
            st.insert( elem(node,nxt,cost) );
            //st.insert( {node,nxt,cost} );
        }
    }

    /*
    for (int i = 1;i <= N;++i) {
        pv(lung[i]);pn;
    }
    //*/

    out << costAPM << '\n' << N-1 << '\n';
    for (int i = 1;i < sol.size();++i) {
        auto p = sol[i];
        out << p.x << ' ' << p.y << '\n';
    }

    return 0;
}