/**APM-Prim**/
#include<bits/stdc++.h>
using namespace std;

const int maxN=(2e5)+5;
int dp[maxN],pre[maxN];

struct tip
{
    int nod;
    bool operator<(const tip&other) const
    {
        if(dp[nod]==dp[other.nod]) return nod<other.nod;
        return dp[nod]<dp[other.nod];
    }
};

set<tip> q;



int n,m,x,y,z;
vector<pair<int,int> > edges,v[maxN];

const int inf=(1e9);
int sol;
bool seen[maxN],inSet[maxN];


int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);


    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);

        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }

    dp[1]=0;

    for(int i=2;i<=n;i++)
        dp[i]=inf;


    q.insert({1});
    inSet[1]=1;

    int nodes=0;
    while(!q.empty())
    {
        int nod=(*q.begin()).nod;
        int cost=dp[nod];

        q.erase(q.begin());

     //   if(cost>dp[nod]) continue;
        seen[nod]=1;
        sol+=cost;
        if(nod!=1)
            edges.push_back(make_pair(pre[nod],nod));

        for(auto it:v[nod])
        {
            int z=it.second;
            if(seen[it.first]) continue;
            if(dp[it.first]>z)
            {
                if(inSet[it.first]) q.erase({it.first});
                    else inSet[it.first]=1;
                pre[it.first]=nod;
                dp[it.first]=z;
                q.insert({it.first});
       //         q.push({it.first,dp[it.first]});

            }
        }
    }

    printf("%d\n",sol);
    printf("%d\n",n-1);
    for(auto it:edges)
        printf("%d %d\n",it.first,it.second);

    return 0;
}