#include<bits/stdc++.h>
using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");


struct to
{
    int destination,cost;
};

struct info
{
    int from,to,cost;
};
struct info_compare
{
    bool operator() (const info& a,const info&b) const
    {
        return a.cost<b.cost;
    }
};

vector<to> graph[200000];
multiset <info,info_compare> que;
int node_count,edge_count;

bool visited[200000];


void read()
{
    in>>node_count>>edge_count;
    int a,b,c;
    for(int i=0; i<edge_count; i++)
    {
        in>>a>>b>>c;
        graph[a-1].push_back({b-1,c});
        graph[b-1].push_back({a-1,c});
    }
}

void solve()
{
    visited[0]=true;
    for(int i=0; i<graph[0].size(); i++)
    {
        info there= {0,graph[0][i].destination,graph[0][i].cost};
        que.insert(there);
    }

    vector<std::pair<int,int>> results;

    int cost=0;
    while(que.size())
    {
        info here=*que.begin();
        que.erase(que.begin());

        if(!visited[here.to])
        {
            visited[here.to]=true;
            cost+=here.cost;
            results.push_back({here.from+1,here.to+1});

            for(int i=0; i<graph[here.to].size(); i++)
            {
                int there=graph[here.to][i].destination;
                int newcost=graph[here.to][i].cost;

                if(!visited[there])
                {
                    que.insert({here.to,there,newcost});
                }

            }
        }



    }
    out<<cost<<endl<<results.size()<<'\n';
    for(int i=0; i<results.size(); i++)
    {
        out<<results[i].first<<" "<<results[i].second<<'\n';
    }



}


int main()
{
    read();
    solve();

    return 0;
}