#include <bits/stdc++.h>

using namespace std;

class Node
{
public:
    int node;
    int cost;

public:

    void initialize(int x, int y)
    {
        node = x;
        cost = y;
    }

    Node()
    {}

    Node(int x, int y)
    {
        initialize(x, y);
    }
};

class Edge
{
public:
    int x;
    int y;
    int cost;

public:
    void initialize(int X, int Y, int C)
    {
        x = X;
        y = Y;
        cost = C;
    }

    Edge()
    {}

    Edge(int x,int y,int c)
    {
        initialize(x, y, c);
    }
};

class Comp
{
public:
    bool operator() (Edge a, Edge b)
    {
        return a.cost > b.cost;
    }
};

void add_edges(int node, priority_queue<Edge, vector<Edge>, Comp> &q, vector <bool> &viz, vector <vector <Node>> &path)
{
    Node vec;
    for(unsigned i = 0; i < path[node].size(); i++)
    {
        vec = path[node][i];
        cout<<vec.node<<' ';
        if(!viz[vec.node])
        {
            q.push(Edge(node, vec.node, vec.cost));
        }
    }

    cout<<'\n';
}


void apm(int start, int &min_cost, vector <Edge> &apm_edges, vector <bool> &viz, vector <vector <Node>> &path)
{
    priority_queue<Edge, vector<Edge>, Comp> q;
    viz[start] = true;
    add_edges(start, q, viz, path);

    Edge cur;

    while(!q.empty())
    {
        cur = q.top();
        q.pop();

        if(!viz[cur.y])
        {
            viz[cur.y] = true;
            min_cost += cur.cost;
            apm_edges.push_back(cur);
            add_edges(cur.y, q, viz, path);
        }
    }


}

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


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

    vector <vector <Node>> path(n + 1);
    vector <bool> viz(n + 1, false);
    vector <Edge> apm_edges;

    int x, y, cost;
    for(; m; m--)
    {
        fin>>x>>y>>cost;

        path[x].push_back(Node(y, cost));
        path[y].push_back(Node(x, cost));
    }

    int min_cost = 0;

    apm(1, min_cost, apm_edges, viz, path);

    fout<<min_cost<<'\n'<<apm_edges.size()<<'\n';

    for(unsigned i = 0; i < apm_edges.size(); i++)
    {
        fout<<apm_edges[i].x<<' '<<apm_edges[i].y<<'\n';
    }

    return 0;
}