#include <bits/stdc++.h>

#define VMAX 100
#define NMAX 200000
#define LOG 18
#define INF (long long)(10e17)
#define MOD 998244353
#define ll long long int


#define NIL 0


using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

vector<pair<int,ll>> adj[NMAX+1];
bool vis[NMAX+1];
pair<ll,int> minW[NMAX+1];

bool cmp(pair<ll,int> a,pair<ll,int> b)
{
    return a.first > b.first;
}

vector<pair<int,int>> apm;

int main()
{
    int n,m;
    fin >> n >> m;

    while(m--)
    {
        int x,y,c;
        fin >> x >> y >> c;
        adj[x].push_back({y,c});
        adj[y].push_back({x,c});
    }

    /// {w,to}, vis[to]=1;

    vector<pair<ll,int>> PQ;
    for(int i=1;i<=n;i++)
    {
        minW[i]={INF,-1};
    }
    minW[1]={0,-1};
    PQ.push_back({0,1});

    ll minCost=0;
    while(!PQ.empty())
    {
        pop_heap(PQ.begin(),PQ.end(),cmp);
        int x = PQ.back().second;
        PQ.pop_back();

        if(!vis[x])
        {
            if(minW[x].second != -1)
            {
                minCost += minW[x].first;
                apm.push_back({x,minW[x].second});
            }
            for(auto e : adj[x])
            {
                if(!vis[e.first] && minW[e.first].first > e.second)
                {
                    minW[e.first] = {e.second,x};
                    PQ.push_back({e.second,e.first});
                    push_heap(PQ.begin(),PQ.end(),cmp);
                }
            }
            vis[x]=1;
        }

    }

    fout << minCost << "\n";
    fout << apm.size() << "\n";
    for(auto e : apm)
    {
        fout << e.first << " " << e.second << "\n";
    }


}