#include <cstdio>
#include <queue>
#include <vector>
#define NMAX 200000
#define inf 0x3f3f3f3f
using namespace std;

int n,m,i,D[NMAX+5],T[NMAX+5],sum;
bool used[NMAX+5];
vector < pair < int, int> > G[NMAX+5];
priority_queue < pair < int, int> , vector <pair < int, int> >, greater <pair < int, int> > >H;

void solve()
{
    int node,i,s,son,cost;
    for(i=2; i<=n; ++i)
        D[i]=inf;
    H.push(make_pair(0,1));
    while(!H.empty())
    {
        node=H.top().second;
        H.pop();
        used[node]=1;
        if(!G[node].empty())
        {
            s=G[node].size();
            for(i=0; i<s; ++i)
            {
                son=G[node][i].second;
                cost=G[node][i].first;
                if(!used[son] && D[son]>cost)
                {
                    H.push(make_pair(cost,son));
                    D[son]=cost;
                    T[son]=node;
                }
            }
        }
    }
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1; i<=m; ++i)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        G[x].push_back(make_pair(c,y));
        G[y].push_back(make_pair(c,x));
    }
    solve();
    for(i=2;i<=n;++i)
      sum+=D[i];
    printf("%d\n%d\n",sum,n-1);
    for(i=2;i<=n;++i)
      printf("%d %d\n",i,T[i]);
    return 0;
}