/* ========================================================================
   $Creator: Emanuel Truta $
   $Notice: (C) Copyright 2016 by Emanuel Truta. All Rights Reserved. $
   ======================================================================== */

#include <vector>
#include <queue>
#include <algorithm>
#include <set>

// #include "manu_header.h"
#include <stdint.h>
typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t i8;
typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;
typedef int32_t b32;

#define internal static
#define local_persist static
#define global_variable static

#define Assert(Expression) if (!(Expression)) { *((int *)0) = 0; }
// manu_header

// #include "graph.cpp"
// #include "graph.h"
struct graph
{
    struct edge
    {
        u32 Node;
        i32 Cost;
    };
    typedef std::vector<edge>::iterator iter;
    

    u32 Size; // Holds the size of the
    u32 NEdges;
    b32 Directed; // Set to true if you need a directed graph.
    b32 ProvideReverse; // Set to true if you need the reverse graph.
    b32 StartIndex; // If for some reason you need the graph to be 1-indexed.

    std::vector< std::vector<edge> > Out; // Holds the graph edges.
    std::vector< std::vector<edge> > In; // Holds the reversed graph edges, if ProvideReverse is not 0. Holds nothing otherwise.
    

    // Reads a graph from a file. The file should have the format:
    // Size NumberOfEdges
    // Node1 Node2 Cost
    // Node1 Node2 Cost
    // ...
    void Read(char *Filename);
    b32 HasEdge(u32 Node1, u32 Node2); // Returns a boolean that is true if there is an edge from Node1 to Node2.
    i32 GetCost(u32 Node1, u32 Node2); // Get cost of an edge. If that edge does not exists, it returns 0xcccccccc;
    void SetCost(u32 Node1, u32 Node2, i32 NewCost); // Sets the cost of an edge. If the edge does not exist, nothing happens.


    // Generates a distance vector from Node1. Every entry in that distance is the distance from Node to that entry.
    // If there is no path from Node to a particular entry, then the distance vector will hold 0x3f3f3f3f for that entry.
    std::vector<u32> DoForwardBFS(u32 Node);
    std::vector<u32> DoBackwardBFS(u32 Node); // Same as DoForwardBFS, but does everything on the reversed graph.
    std::vector<u32> DoDijkstra(u32 Node); // Same as DoForwardBFS, but uses Dijkstra algorithm.
    u32 GetDistanceForwardBFS(u32 Node1, u32 Node2); // Gets the smallest path from Node1 to Node2 using ForwardBFS.
    u32 GetDistanceBackwardBFS(u32 Node1, u32 Node2); // Gets the smallest path from Node1 to Node2 using BackwardBFS.
    u32 GetDistanceDijkstra(u32 Node1, u32 Node2); // Gets the smallest path from Node1 to Node2 using Dijkstra.
    std::vector<u32> GetTopologicalSort();
};
// graph.h

// <parsing>
FILE *fin;
const int maxb = 8192;
char buf[maxb];
int ptr = maxb - 1;
 
int GetInt()
{
    int mul = 1;
    while (buf[ptr] < '0' || '9' < buf[ptr])
    {
        if (buf[ptr] == '-')
        {
            mul = -1;
        }
        if (++ptr >= maxb)
        {
            fread(buf, maxb, 1, fin);
            ptr = 0;
        }
    }
    int nr = 0;
    while ('0' <= buf[ptr] && buf[ptr] <= '9')
    {
        nr = nr * 10 + buf[ptr] - '0';
        if (++ptr >= maxb)
        {
            fread(buf, maxb, 1, fin);
            ptr = 0;
        }
    }
    return nr * mul;
} 
// </parsing>

void graph::
Read(char *Filename)
{
    // FILE *File = fopen(Filename, "r");
    fin = fopen(Filename, "r");

    u32 EdgesCount;
    // fscanf(File, "%d %d\n", &Size, &EdgesCount);
    Size = GetInt(); EdgesCount = GetInt(); NEdges = EdgesCount;
    Size += StartIndex;
    Out.resize(Size);
    if (ProvideReverse)
    {
        In.resize(Size);
    }

    for (u32 Index = 0; Index < EdgesCount; ++Index)
    {
        u32 X, Y;
        i32 Cost;

        // fscanf(File, "%d %d %d\n", &X, &Y, &Cost);
        X = GetInt(); Y = GetInt(); Cost = GetInt();

        if (Directed)
        {
            Out[X].push_back(edge{Y, Cost});
            if (ProvideReverse)
            {
                In[Y].push_back(edge{X, Cost});
            }
        }
        else
        {
            Out[X].push_back(edge{Y, Cost});
            Out[Y].push_back(edge{X, Cost});
        }
    }
}


b32 graph::
HasEdge(u32 Node1, u32 Node2)
{
    b32 Result = 0;

    for (iter It = Out[Node1].begin(); It != Out[Node1].end(); ++It)
    {
        if (It->Node == Node2)
        {
            Result = 1;
        }
    }
    
    return Result;
}


i32 graph::
GetCost(u32 Node1, u32 Node2)
{
    for (iter It = Out[Node1].begin(); It != Out[Node1].end(); ++It)
    {
        if (It->Node == Node2)
        {
            return It->Cost;
        }
    }

    return 0xcccccccc;
}


void graph::
SetCost(u32 Node1, u32 Node2, i32 NewCost)
{
    for (iter It = Out[Node1].begin(); It != Out[Node1].end(); ++It)
    {
        if (It->Node == Node2)
        {
            It->Cost = NewCost;
        }
    }

    if (Directed && ProvideReverse)
    {
        for (iter It = In[Node2].begin(); It != In[Node2].end(); ++It)
        {
            if (It->Node == Node1)
            {
                It->Cost = NewCost;
            }
        }
    }

    if (!Directed)
    {
        for (iter It = Out[Node2].begin(); It != Out[Node2].end(); ++It)
        {
            if (It->Node == Node1)
            {
                It->Cost = NewCost;
            }
        }
    }
}


std::vector<u32> graph::
DoForwardBFS(u32 Node)
{
    std::vector<u32> Dist;
    Dist.resize(Size);
    for (u32 I = 0; I < Size; ++I)
    {
        Dist[I] = 0x3f3f3f3f;
    }
    Dist[Node] = 0;

    std::queue<u32> Q;
    Q.push(Node);
    while (!Q.empty())
    {
        u32 Node = Q.front();
        Q.pop();

        for (u32 I = 0; I < Out[Node].size(); ++I)
        {
            if (Dist[Out[Node][I].Node] > Dist[Node] + 1)
            {
                Dist[Out[Node][I].Node] = Dist[Node] + 1;
                Q.push(Out[Node][I].Node);
            }
        }
    }
    
    return Dist;
}

std::vector<u32> graph::
DoBackwardBFS(u32 Node)
{
    std::vector<u32> Dist;
    if (!ProvideReverse)
    {
        printf("ERROR: ProvideReverse is 0 and you called DoBackwardBFS.\n");
        return Dist;
    }
    Dist.resize(Size);
    for (u32 I = 0; I < Size; ++I)
    {
        Dist[I] = 0x3f3f3f3f;
    }
    Dist[Node] = 0;

    if (!ProvideReverse)
    {
        return Dist;
    }

    std::queue<u32> Q;
    Q.push(Node);
    while (!Q.empty())
    {
        u32 Node = Q.front();
        Q.pop();

        for (u32 I = 0; I < In[Node].size(); ++I)
        {
            if (Dist[In[Node][I].Node] > Dist[Node] + 1)
            {
                Dist[In[Node][I].Node] = Dist[Node] + 1;
                Q.push(In[Node][I].Node);
            }
        }
    }
    
    return Dist;
}

std::vector<u32> graph::
DoDijkstra(u32 Node)
{
    std::vector<b32> Viz;
    std::vector<u32> Dist;
    Viz.resize(Size);
    Dist.resize(Size);
    for (u32 I = 0; I < Size; ++I)
    {
        Dist[I] = 0x3f3f3f3f;
        Viz[I] = 0;
    }
    Dist[Node] = 0;

    std::priority_queue< std::pair<i32, u32> > PQ;
    PQ.push(std::make_pair(0, Node));
    while (!PQ.empty())
    {
        u32 Node = PQ.top().second;
        PQ.pop();

        if (Viz[Node])
        {
            continue;
        }
        Viz[Node] = 1;

        for (u32 I = 0; I < Out[Node].size(); ++I)
        {
            if (Dist[Out[Node][I].Node] > Dist[Node] + Out[Node][I].Cost)
            {
                Dist[Out[Node][I].Node] = Dist[Node] + Out[Node][I].Cost;
                PQ.push(std::make_pair(-Dist[Out[Node][I].Node], Out[Node][I].Node));
            }
        }
    }
    return Dist;
}

u32 graph::
GetDistanceForwardBFS(u32 Node1, u32 Node2)
{
    std::vector<u32> Dist = DoForwardBFS(Node1);
    return Dist[Node2];
}

u32 graph::
GetDistanceBackwardBFS(u32 Node1, u32 Node2)
{
    std::vector<u32> Dist = DoBackwardBFS(Node2);
    return Dist[Node1];
}

u32 graph::
GetDistanceDijkstra(u32 Node1, u32 Node2)
{
    std::vector<u32> Dist = DoDijkstra(Node1);
    return Dist[Node2];
}
// graph.cpp

int main()
{
    printf("====================\n");

    graph Graph = {};
    Graph.StartIndex = 1;
    Graph.Read("apm.in");


    std::vector< std::pair<int, int > > Solution;
    u32 SolutionCost = 0;
    std::set<int> Set;
    std::priority_queue< std::pair<i32, std::pair<u32 ,u32> > > PQ;
    
    Set.insert(1);
    for (int I = 0; I < Graph.Out[1].size(); ++I)
    {
        PQ.push(std::make_pair(-Graph.Out[1][I].Cost,
                               std::make_pair(1, Graph.Out[1][I].Node)));
        // printf("%d %d %d\n", 1, Graph.Out[1][I].Node, -Graph.Out[1][I].Cost);
    }
    // printf("=====\n");
    // printf("%d\n", PQ.top().first);
    

    while (!PQ.empty())
    {
        u32 Cost = -PQ.top().first;
        u32 Node1 = PQ.top().second.first;
        u32 Node2 = PQ.top().second.second;
        PQ.pop();

        // for (std::set<int>::iterator it = Set.begin(); it != Set.end(); ++it)
        // {
        //     printf("%d ", *it);
        // }
        // printf("\n%d %d %d\n\n", Node1, Node2, Cost);

        if (Set.find(Node1) != Set.end() &&
            Set.find(Node2) != Set.end())
        {
            continue;
        }

        if (Set.find(Node1) == Set.end())
        {
            for (int I = 0; I < Graph.Out[Node1].size(); ++I)
            {
                PQ.push(std::make_pair(-Graph.Out[Node1][I].Cost,
                                       std::make_pair(Node1, Graph.Out[Node1][I].Node)));
            }
            Solution.push_back(std::make_pair(Node1, Node2));
            SolutionCost += Cost;
            Set.insert(Node1);
        }
        
        if (Set.find(Node2) == Set.end())
        {
            for (int I = 0; I < Graph.Out[Node2].size(); ++I)
            {
                PQ.push(std::make_pair(-Graph.Out[Node2][I].Cost,
                                       std::make_pair(Node2, Graph.Out[Node2][I].Node)));
            }
            Solution.push_back(std::make_pair(Node1, Node2));
            SolutionCost += Cost;
            Set.insert(Node2);
        }
    }

    FILE *Out = fopen("apm.out", "w");
    fprintf(Out, "%d\n", SolutionCost);
    fprintf(Out, "%d\n", Solution.size());
    for (int I = 0; I < Solution.size(); ++I)
    {
        fprintf(Out, "%d %d %d\n", Solution[I].first, Solution[I].second,
                Graph.GetCost(Solution[I].first, Solution[I].second));
    }


    return 0;
}