#include<algorithm>
#include<iostream>
#include<fstream>
#include<vector>
#include<set>
#define DN 200010
using namespace std;
fstream fin("apm.in",ios::in),fout("apm.out",ios::out);

struct strm
{
    int c,x;
    bool operator < (const strm &f) const
    {
        return c<f.c;
    }
};
struct strv
{
    int y,c;
};

vector<strv> v[DN],r;
multiset<strm> heap;
int n,m,d[DN],t[DN],ap[DN];

int main()
{
    int i,j,tx,ty,x,y,c,total=0;
    fin>>n>>m;
    for(i=1;i<=n;i++) d[i]=DN*10000;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        v[x].push_back({y,c});
        v[y].push_back({x,c});
    }
    d[1]=0;
    t[1]=1;
    heap.insert({0,1});
    while(heap.empty()==0)
    {
        x=(*heap.begin()).x;
        c=(*heap.begin()).c;
        heap.erase(heap.begin());
        if(ap[x]==1) continue ;
        ap[x]=1;
        total+=c;

        r.push_back({t[x],x});
        for(auto j:v[x])
        {
            if(d[j.y]>j.c)
            {
                t[j.y]=x;
                d[j.y]=j.c;
                heap.insert({d[j.y],j.y});
            }
        }
    }
    fout<<total<<"\n";
    fout<<r.size()-1<<"\n";
    for(i=1;i<r.size();i++)
    {
        fout<<r[i].y<<" "<<r[i].c<<"\n";
    }
}