#include <fstream>
#include <vector>
#include <set>
#define f first
#define s second
const int NMAX=200055;

using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");

struct edge
{
    int a, b, c;
    bool operator<(const edge& other) const
    {
        return c<other.c;
    }
};

vector <edge> v[NMAX];
vector <pair<int, int>> mm, ans;
int n, m;
pair<int, int> mini[NMAX];
set <pair<int, int>> s;

void apm();

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int i, a, b, c;
    cin>>n>>m;
    for(i=0; i<m; i++)
    {
        cin>>a>>b>>c;
        v[a].push_back({b, c, i});
        v[b].push_back({a, c, i});
        mm.push_back({a, b});
    }
    apm();
    return 0;
}

void apm()
{
    int i, cost=0;
    pair<int, int> p;
    mini[1]={-1e9, 0};
    for(i=2; i<=n; i++) mini[i]={1e9, 0};
    for(auto i:v[1])
    {
        if(mini[i.a].f>i.b)
        {
            mini[i.a].f=i.b;
            mini[i.a].s=i.c;
            s.insert({mini[i.a].f, i.a});
        }
    }
    while(!s.empty())
    {
        p=*s.begin(); s.erase(s.begin());
        mini[p.s].f=-1e9;
        cost+=p.f;
        ans.push_back(mm[mini[p.s].s]);
        for(auto i:v[p.s])
        {
            if(mini[i.a].f>i.b)
            {
                if(mini[i.a].f!=1e9) s.erase(s.find({mini[i.a].f, i.a}));
                mini[i.a].f=i.b;
                mini[i.a].s=i.c;
                s.insert({mini[i.a].f, i.a});
            }
        }
    }
    cout<<cost<<'\n';
    cout<<ans.size()<<'\n';
    for(auto i:ans) cout<<i.f<<' '<<i.s<<'\n';
}