#include<iostream>
#include<fstream>
#include<vector>
#define INF 2002
using namespace std;
struct elem
{
    int y;
    int c;
};
void insheap(int ans[],int &n,int v,vector <int> &cheie,vector <int> &q)
{
    int p,t;
    n++;
    p=n;
    ans[p]=v;
    q[v]=p;
    while(p>1)
    {
        t=p/2;
        if (cheie[ans[p]]>=cheie[ans[t]]) return;
            else
                {
                    swap(ans[p],ans[t]);
                    swap(q[ans[p]],q[ans[t]]);
                    p=t;
                }
    }
}
int delheap(int ans[],int &n,vector <int> &q,vector <int> &cheie)
{
    int v=ans[1];
    q[v]=0;
    ans[1]=ans[n];
    q[ans[1]]=1;
    n--;
    int i=1;
    while(2*i<=n||2*i+1<=n)
    {
        if(cheie[ans[i]]>cheie[ans[2*i]]||cheie[ans[i]]>cheie[ans[2*i+1]])
                if(cheie[ans[2*i]]<cheie[ans[2*i+1]]) {swap(ans[2*i],ans[i]);swap(q[ans[2*i]],q[ans[i]]);i=2*i;}
                        else {swap(ans[2*i+1],ans[i]);swap(q[ans[2*i+1]],q[ans[i]]);i=2*i+1;}
            else i=i*2;
    }
    return v;
}
void actualizare (int ans[],int p,vector <int> &q,vector <int> &cheie)
{
    while(p>1)
    {
        int t=p/2;
        if (cheie[ans[p]]>=cheie[ans[t]]) return;
            else
                {
                    swap(ans[p],ans[t]);
                    swap(q[ans[p]],q[ans[t]]);
                    p=t;
                }
    }
}
void apm_prim(vector <elem> G[],int n,int r,int *p,int &s)
{
    vector <int> q(n+1,0);
    vector <int> cheie(n+1,INF);
    cheie[r]=0;
    int ans[n+1],nn=0,i;
    for(int i=1;i<=n;i++) insheap(ans,nn,i,cheie,q);
    p[r]=0;
    while(nn)
    {
        int u=delheap(ans,nn,q,cheie);
        s+=cheie[u];
        for(i=0;i<G[u].size();i++)
            if(q[G[u][i].y]!=0&&G[u][i].c<cheie[G[u][i].y])
            {
                    p[G[u][i].y]=u;
                    cheie[G[u][i].y]=G[u][i].c;
                    actualizare(ans,q[G[u][i].y],q,cheie);
            }
    }
}

int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int n,m,i,j,x,s=0;
    f>>n>>m;
    vector <elem> G[n+1];
    int *p;
    p=new int[n+1];
    for(i=0;i<m;i++)
    {
        elem z;
        f>>x>>z.y>>z.c;
        G[x].push_back(z);
        j=z.y;z.y=x;
        G[j].push_back(z);
    }
    apm_prim(G,n,1,p,s);
    g<<s<<'\n'<<n-1<<'\n';
    for(int i=1;i<=n;i++) if(p[i]) g<<i<<" "<<p[i]<<"\n";
    f.close();
    g.close();
    return 0;
}