#include <iostream>
#include <vector>
#define maxm 400005
#include <cstdio>
#include <queue>

using namespace std;

int s,n,m,viz[200005],nr;
priority_queue < pair <int , pair <int ,int > > > q;
vector < pair <int ,int  > > g[200005] ;
vector < pair <int ,int > > sol;
void read()
{
    scanf("%d%d",&n,&m);
    int x,y,c;
    for (int i=1; i<=m; ++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        g[x].push_back(make_pair(y,c));
        g[y].push_back(make_pair(x,c));
    }
}

void rezolv()
{
    viz[1]=true;
    for (vector <pair < int ,int > >:: iterator it=g[1].begin();it!=g[1].end();++it)
        q.push(make_pair(-it->second,make_pair(1,it->first)));
    while(!q.empty())
    {
        int x=q.top().second.first;
        int y=q.top().second.second;
        int c=-q.top().first;
        q.pop();
        if (viz[y])
            continue;
        viz[y]=1;
        sol.push_back(make_pair(x,y));
        s+=c;
        for (vector <pair < int ,int > >:: iterator it=g[y].begin();it!=g[y].end();++it)
            if (!viz[it->first])
                q.push(make_pair(-it->second,make_pair(y,it->first)));
    }
    printf("%d\n%d\n",s,n-1);
    for (vector <pair <int ,int > > :: iterator it=sol.begin() ; it!=sol.end(); ++it)
        printf("%d %d\n", it->second,it->first);
}

int main()
{

    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    read();
    rezolv();
    return 0;
}