#include<stdio.h>
#include<vector>
#include<queue>
#define INF 10000001
#define Nmx 200005

using namespace std;

int n,m;
vector<pair<int,int> > G[Nmx];
int viz[Nmx],cost[Nmx],ns;
struct dat{
    int x,y;
}sol[Nmx*2];

struct cmp
{
    bool operator()(const int &a,const int &b) const
    {
        return cost[a]>cost[b];
    }
};
priority_queue<int, vector<int>, cmp> Q;

void citire()
{
    int x,y,c;
    scanf("%d%d",&n,&m);
    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 solve()
{
    vector< pair<int,int> > ::iterator it;
    for(int i=1;i<=n;++i)
        cost[i]=viz[i]=INF;
    viz[1]=0;
    cost[1]=0;
    Q.push(1);
    int sum=0;
    for(int i=1;i<=n;++i)
    {
        int nod=Q.top();
        viz[nod]=-1;
        Q.pop();
        sum+=cost[nod];
        int min=INF,pzz=0;
        for(it=G[nod].begin();it!=G[nod].end();++it)
        {
          if(viz[it->first]==-1)
            {
               if(it->second<min)
               {
                    min=it->second;
                    pzz=it->first;
               }
               continue;
           }
          if(cost[it->first]>it->second )
           {
               cost[it->first]=it->second;
               if( INF == viz[it->first] )
               {
                   Q.push(it->first);
                   viz[it->first]=1;
               }
            }
        }
        if(i>1)
        {
            sol[++ns].x=nod;
            sol[ns].y=pzz;
        }
    }
    printf("%d\n%d\n",sum,ns);
    for(int i=1;i<=ns;++i)
        printf("%d %d\n",sol[i].x,sol[i].y);
}

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