/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package alg;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

/**
 *
 * @author marek
 */
public class Main {

    public static void main(String[] args) throws IOException {
        initFILE("datapub/pub05.in");
//        initSTND();

        int n = Reader.nextInt();
        int m = Reader.nextInt();

        new Graph(n);
        for (int i = 0; i < n; i++) {
            Graph.nodes[i] = new Node(i);
        }

        int c1, c2, c3;
        for (int i = 0; i < m; i++) {

            c1 = Reader.nextInt();
            c2 = Reader.nextInt();
            c3 = Reader.nextInt();
            Graph.nodes[c1].addEdge(c2, c3);
            Graph.nodes[c2].addIn(c1);

            if (c3 > Graph.maxLength) {
                Graph.results = new ArrayList<>();

                Graph.results.add(new Result(c1, c2));
                Graph.maxLength = c3;
            } else if (c3 == Graph.maxLength) {
                Graph.results.add(new Result(c1, c2));
            }
        }

        Graph.start();

        printSortedResults();
    }

    public static void printSortedResults() {
        Collections.sort(Graph.results, new Comparator<Result>() {

            @Override
            public int compare(Result o1, Result o2) {
                int i = o1.c1 - o2.c1;
                return (i == 0) ? o1.c2 - o2.c2 : i;
            }
        });

        for (Result result : Graph.results) {
            System.out.println(result.c1 + " " + result.c2);
        }
    }

    public static void initSTND() throws IOException {
        Reader.init(System.in);
    }

    public static void initFILE(String file) throws FileNotFoundException, IOException {
        Reader.init(new FileInputStream(file));
//        Reader.init(new FileInputStream("datapub/private"));
    }
}


====================================================

package alg;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 *
 * @author marek
 */
public class Graph {

    static HashSet<Integer> miss = new HashSet<>();

    static Node[] nodes;

    static int maxLength = 0;

    static List<Result> results = new ArrayList<>();

    public Graph(int numberOfNodes) {
        nodes = new Node[numberOfNodes];
    }

    public static void start() {

        for (Node node : nodes) {
            if (!miss.contains(node.localKey)) {
                node.evaluateOut();
            }

        }

    }
}

class Result  {

    int c1;
    int c2;

    public Result(int c1, int c2) {
        this.c1 = c1;
        this.c2 = c2;
    }

}

================================================

package alg;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class Node {

    static int i = 0;

    int localKey;

    int oneout;
    int oneoutv;

    HashSet<Integer> in = new HashSet<>();
    HashMap<Integer, Integer> values = new HashMap<>();
    HashMap<Integer, Integer> out = new HashMap<>();

    public Node(int key) {
        this.localKey = key;

    }

    public void addEdge(int key, int value) {
        out.put(key, value);

        if (out.size() == 1) {
            oneout = key;
            oneoutv = value;
        } else if (out.size() == 2) {
            values.put(localKey, 0);
        }
    }

    public void addIn(int key) {
        in.add(key);
    }

    private void addValues(HashMap<Integer, Integer> map, int plusEdge) {
        if (in.size() == 1 && out.size() == 1) {
            Graph.miss.add(localKey);
            Graph.nodes[oneout].addValues(map, plusEdge + oneoutv);
        } else {
            Integer key;
            Integer value;
            Integer v2;
            int newValue;
            for (Map.Entry<Integer, Integer> entrySet : map.entrySet()) {
                key = entrySet.getKey();
                value = entrySet.getValue();

                newValue = value + plusEdge;
                if ((values.containsKey(key))) {

                    if (values.get(key) <= newValue) {
                        values.put(key, newValue);

                    }

                } else {
                    values.put(key, newValue);

                }

                if (in.contains(key)) {

                    if (newValue >= Graph.maxLength) {
                        if (newValue > Graph.maxLength) {
                            Graph.maxLength = newValue;

                            Graph.results = new ArrayList<>();

                        }
//                                System.out.println("add " + key + " + " + localKey);
                        Graph.results.add(new Result(key, localKey));
                    }
                }
            }
        }

    }

    public void evaluateOut() {

        for (Map.Entry<Integer, Integer> entrySet : out.entrySet()) {
            Integer key = entrySet.getKey();
            Integer value = entrySet.getValue();

            Graph.nodes[key].addValues(values, value);

        }
    }

}