package Java;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Suurbale {
    static class Vertex implements Comparable<Vertex> {
        public int index;
        public int distance;

        Vertex(int index, int distance) {
            this.index = index;
            this.distance = distance;
        }

        public int compareTo(Vertex other) {
            if (this.distance == other.distance)
                return Integer.compare(this.index, other.index);
            return Integer.compare(this.distance, other.distance);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int vertexCount = Integer.parseInt(reader.readLine());
        int edgeCount = Integer.parseInt(reader.readLine());

        HashMap<Integer, Vertex> vertices = new HashMap<>();
        HashMap<Integer, TreeSet<Integer>> paths = new HashMap<>();
        LinkedHashMap<Integer, LinkedHashMap<Integer, Integer>> graph = new LinkedHashMap<>(vertexCount);

        for (int i = 0; i < vertexCount; i++) {
            // initialize
            vertices.put(i, new Vertex(i, Integer.MAX_VALUE));
            graph.put(i, new LinkedHashMap<Integer, Integer>());
            paths.put(i, new TreeSet<Integer>());
        }

        for (int i = 0; i < edgeCount; i++) {
            String[] tokens = reader.readLine().split(" ");
            int start = Integer.parseInt(tokens[0]);
            int end = Integer.parseInt(tokens[1]);
            int weight = Integer.parseInt(tokens[2]);

            graph.get(start).put(end, weight);
            graph.get(end).put(start, weight);
        }

        int[] potentials = new int[vertexCount];
        int[] previous = dijkstra(vertices, graph, potentials);
        storePath(graph, previous, paths);
        reversePath(graph, previous);
        for (int i = 0; i < potentials.length; i++) {
            potentials[i] = vertices.get(i).distance;
        }
        previous = dijkstra(vertices, graph, potentials);
        storePath(graph, previous, paths);
        ArrayList<String> firstPath = getPath(paths);
        ArrayList<String> secondPath = getPath(paths);

        System.out.println(String.join(" -> ", firstPath));
        System.out.println(String.join(" -> ", secondPath));
    }

    public static int[] dijkstra(HashMap<Integer, Vertex> vertices,
            LinkedHashMap<Integer, LinkedHashMap<Integer, Integer>> graph, int[] potentials) {
        int[] previous = new int[vertices.size()];
        for (int i = 0; i < previous.length; i++) {
            previous[i] = -1;
        }
        for (Vertex vertex : vertices.values()) {
            vertex.distance = Integer.MAX_VALUE;
        }

        Vertex start = vertices.get(0);
        start.distance = 0;
        TreeSet<Vertex> priorityQueue = new TreeSet<>();
        priorityQueue.add(start);

        while (!priorityQueue.isEmpty()) {
            Vertex current = priorityQueue.pollFirst();
            for (Map.Entry<Integer, Integer> entry : graph.get(current.index).entrySet()) {
                int nextsIndex = entry.getKey();
                int edgeWeight = entry.getValue();
                Vertex neighbour = vertices.get(nextsIndex);
                int newDistance = current.distance + edgeWeight + potentials[current.index] - potentials[nextsIndex];
                if (newDistance < neighbour.distance) {
                    priorityQueue.remove(neighbour);
                    neighbour.distance = newDistance;
                    previous[neighbour.index] = current.index;
                    priorityQueue.add(neighbour);
                }
            }
        }

        return previous;
    }

    public static void reversePath(LinkedHashMap<Integer, LinkedHashMap<Integer, Integer>> graph, int[] previous) {
        int element = previous.length - 1;
        int parent = previous[previous.length - 1];
        while (parent != -1) {
            int weight = graph.get(element).get(parent);
            graph.get(parent).remove(element);
            graph.get(element).remove(parent);

            graph.get(element).put(parent, -weight);
            element = parent;
            parent = previous[parent];
        }

    }

    public static void storePath(LinkedHashMap<Integer, LinkedHashMap<Integer, Integer>> graph, int[] previous,
            HashMap<Integer, TreeSet<Integer>> paths) {
        int element = previous.length - 1;
        int parent = previous[previous.length - 1];
        while (parent != -1) {

            if (paths.get(element).contains(parent)) {
                paths.get(element).remove(parent);
            } else {
                paths.get(parent).add(element);
            }
            element = parent;
            parent = previous[parent];
        }
    }

    public static ArrayList<String> getPath(HashMap<Integer, TreeSet<Integer>> paths) {
        int start = 0;
        int end = paths.size() - 1;
        ArrayList<String> path = new ArrayList<>();
        int cur = start;
        while (cur != end) {
            path.add(String.valueOf(cur));
            int next = paths.get(cur).first();
            paths.get(cur).remove(next);
            cur = next;
        }
        path.add(String.valueOf(end));
        return path;
    }
}