#include <fstream>
#include <vector>
#include <set>
#define INF 2000000000
using namespace std;
ifstream fin ("apm.in");
ofstream fout("apm.out");
int n,m,i,j,p,t[200001],D[200001],sol,nr,x,y,cost,vecin;
vector <pair<int,int>> L[400001];
set <pair<int,int>> S;
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        L[x].push_back({y,cost});
        L[y].push_back({x,cost});
    }
    for(i=1;i<=n;i++)
        D[i]=INF;
    D[1]=0;
    S.insert({0,1});
    while(!S.empty())
    {
        p=S.begin()->second;
        S.erase(S.begin());
        for(j=0;j<L[p].size();j++)
        {
            vecin=L[p][j].first;
            cost=L[p][j].second;
            if(D[vecin]>cost&&t[p]!=vecin)
            {
                S.erase({D[vecin],vecin});
                D[vecin]=cost;
                t[vecin]=p;
                S.insert({D[vecin],vecin});
            }

        }
    }

    for(i=1;i<=n;i++)
        if(t[i])
        {
            nr++;
            sol+=D[i];
        }
    fout<<sol<<"\n";
    fout<<nr<<"\n";
    for(i=1;i<=n;i++)
        if(t[i])
            fout<<i<<" "<<t[i]<<"\n";
    return 0;
}