#include<fstream>
#include<vector>
#include<set>
#define pb push_back
#define mp make_pair

using namespace std;

const int NMAX = 200010;

const int inf = 100000000;

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

vector < pair <int, int> > g[NMAX], APM;
set < pair <int, int> > q;
int n,m,i,j,x,y,z,D[NMAX],V[NMAX],P[NMAX],s=0;

int main()
{
    cin>>n>>m;
    while(m--)
    {
        cin>>x>>y>>z;
        g[x].pb(mp(y,z));
        g[y].pb(mp(x,z));
    }
    for (i=1;i<=n;i++) D[i]=inf, P[i]=-1, V[i]=0;
    V[1]=1; D[1]=0;
    q.insert(mp(0,1));
    for (i=1;i<=n;i++)
    {
        int v=q.begin()->second, len=q.begin()->first;
        q.erase(q.begin());
        V[v]=1;

        if (P[v]!=-1) s+=len, APM.pb(mp(P[v],v));

        for (j=0;j<g[v].size();j++)
        {
            int to=g[v][j].first, cost=g[v][j].second;
            if (D[to]>cost && !V[to])
            {
                P[to]=v;
                q.erase(mp(D[to],to));
                D[to]=cost;
                q.insert(mp(D[to],to));
            }
        }
    }
    cout<<s<<"\n"<<n-1<<"\n";
    for (i=0;i<APM.size();i++) cout<<APM[i].first<<" "<<APM[i].second<<"\n";
    return 0;
}