#include <fstream>
#include <vector>
#define dmax 2000000000
#include <queue>
#include <utility>
#include <bitset>

using namespace std;

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

vector < pair<int, int> > L[400100];

int n,m,i,j,D[200100],l[400100],C[400100],t[400100],sum,nr,x,y,b,c,vmin,poz,S;
pair <int , int > a;
bitset<400100>v,ok;

struct cmp {
    bool operator()(pair<int, int> a, pair<int, int> b) {
        return a.first > b.first;
    }
};
priority_queue<pair<int, int>, vector< pair<int, int> >, cmp> H;

int main()
{
    fin >> n >> m;
    for(i = 1; i <= m; i ++){
        fin >> x >> y >> c;
        L[x].push_back(make_pair(c,y));
        L[y].push_back(make_pair(c,x));
    }
    for(i=1;i<=n;i++)
        D[i]=dmax;

    D[1]=0;
    H.push(make_pair(0, 1));

    while(!H.empty())
    {
        while (!H.empty() && ok[H.top().second] != 0)
        {
            H.pop();
        }
        if (H.empty())
        {
            break;
        }
        pair<int, int> st = H.top();
        H.pop();
        ok[st.second] = 1;

        //D[st.second] = st.first;
        //v[st.second] = 1;
        S += st.first;
        l[++ nr] = t[st.second];
        C[nr] = st.second;

        for(i = 0 ; i < L[st.second].size(); i ++)
        {
            a = L[st.second][i];
            if(D[a.second] > a.first ){
                D[a.second] = a.first;
                H.push(make_pair(D[a.second],a.second));
                t[a.second] = st.second;
            }
        }

    }
        fout << S << '\n' << nr - 1 << '\n';
        for(i = 2; i <= nr; i ++)
            fout << C[i] << " " << l[i] << '\n';

    return 0;
}