#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

// Global declarations
vector<vector<pair<int, int>>> graph;
vector<int> dist;
vector<int> parent;

// Function declarations
void takeInput(int e);
void dijkstra(int source, int n);
void printPath(int node);
void printResult(int n);

int main() {
    int nodes, edges;
    cin >> nodes >> edges;

    graph.resize(nodes + 1);
    dist.resize(nodes + 1);
    parent.resize(nodes + 1);

    takeInput(edges);
    dijkstra(0, nodes);
    printResult(nodes);

    return 0;
}

// Input graph
void takeInput(int e) {
    int u, v, wt;

    for (int i = 0; i < e; i++) {
        cin >> u >> v >> wt;
        graph[u].push_back({v, wt});
        graph[v].push_back({u, wt});
    }
}

// Dijkstra Algorithm
void dijkstra(int source, int n) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    for (int i = 0; i <= n; i++) {
        dist[i] = INF;
        parent[i] = -1;
    }

    dist[source] = 0;
    pq.push({0, source});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        for (auto edge : graph[u]) {
            int v = edge.first;
            int wt = edge.second;

            if (dist[u] + wt < dist[v]) {
                dist[v] = dist[u] + wt;
                parent[v] = u;
                pq.push({dist[v], v});
            }
        }
    }
}

// Print shortest path
void printPath(int node) {
    if (node == -1) return;

    printPath(parent[node]);
    cout << node;

    if (parent[node] != -1)
        cout << " -> ";
}

// Print final result
void printResult(int n) {
    for (int i = 1; i <= n; i++) {
        cout << "Customer " << i << ": ";

        if (dist[i] == INF) {
            cout << "Not reachable" << endl;
        } 
        else {
            cout << "Minimum Distance = " << dist[i] << ", Path = ";
            printPath(i);
            cout << endl;
        }
    }
}