#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

typedef struct edge
{
    int from,to,val;
};

typedef vector<int> VECTOR_OF_INTS;
typedef vector<edge> VECTOR_OF_EDGES;


inline bool compare(const edge &a,const edge &b)
{
    return a.val < b.val;
}

void print_edges(VECTOR_OF_EDGES &E)
{
    for(int i=0;i<E.size();i++)
        cout<<E[i].from<<" "<<E[i].to<<" "<<E[i].val<<endl;
    cout<<endl;
}


void print_nodes(VECTOR_OF_INTS &V)
{
    for(int i=1;i<V.size();i++)
        cout<<V[i]<<" ";
    cout<<endl;
}

int main()
{
    int n,m;
    fin>>n>>m;
    VECTOR_OF_EDGES E;
    VECTOR_OF_INTS V(n+1);

    for(int i=0;i<m;i++)
    {
        edge curr;
        fin>>curr.from>>curr.to>>curr.val;
        E.push_back(curr);
    }

    for(int i=1;i<=n;i++)
        V[i] = i;

    print_edges(E);
    sort(E.begin(),E.end(),compare);
    print_edges(E);

    print_nodes(V);
}