#include <cstdio>
#include <cstring>
#include <queue>

#define mp make_pair
#define INF 0x3f3f3f3f
#define NMAX 200005

using namespace std;

int n,m;
int d[NMAX],viz[NMAX],t[NMAX];
vector<pair<int,int> > g[NMAX];

void read()
{
    int a,b,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&a,&b,&c);
        g[a].push_back(mp(c,b));
        g[b].push_back(mp(c,a));
    }
    memset(d,INF,sizeof(d));
}

void prim()
{
    int k;
    priority_queue<pair<int,int> > h;
    h.push(mp(0,1));
    d[1]=0;
    while(!h.empty())
    {
        k=h.top().second;
        h.pop();
        viz[k]=1;
        for(vector<pair<int,int> >::iterator it=g[k].begin();it!=g[k].end();++it)
            if(!viz[it->second]&&d[it->second]>it->first)
            {
                d[it->second]=it->first;
                h.push(mp(-it->first,it->second));
                t[it->second]=k;
            }
    }
}

void print()
{
    int cost=0;
    for(int i=1;i<=n;++i)
        cost+=d[i];
    printf("%d\n%d\n",cost,n-1);
    for(int i=2;i<=n;++i)
        printf("%d %d\n",i,t[i]);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    read();
    prim();
    print();
    return 0;
}