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

const int INF = 1e9;

// ---------------------- Graph Input ----------------------
void takeInput(int &N, int &E, vector<vector<pair<int,int>>> &graph) {
    cin >> N >> E;

    graph.assign(N + 1, {});

    for (int i = 0; i < E; i++) {
        int u, v, w;
        cin >> u >> v >> w;

        graph[u].push_back({v, w});
        graph[v].push_back({u, w}); // remove if directed
    }
}

// ---------------------- Dijkstra Algorithm ----------------------
void dijkstra(int source,
              vector<vector<pair<int,int>>> &graph,
              vector<int> &dist,
              vector<int> &parent) {

    int n = graph.size();
    dist.assign(n, INF);
    parent.assign(n, -1);

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;

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

    while (!pq.empty()) {
        auto [currentDist, u] = pq.top();
        pq.pop();

        if (currentDist > dist[u]) continue;

        for (auto [v, weight] : graph[u]) {
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                parent[v] = u;
                pq.push({dist[v], v});
            }
        }
    }
}

// ---------------------- Path Printing ----------------------
void printPath(int node, vector<int> &parent) {
    if (node == -1) return;
    printPath(parent[node], parent);
    cout << node;
    if (parent[node] != -1) cout << " -> ";
}

// ---------------------- Output ----------------------
void printResult(int N, vector<int> &dist, vector<int> &parent) {
    for (int i = 1; i <= N; i++) {
        cout << "Customer " << i << ": ";

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

// ---------------------- Main ----------------------
int main() {
    int N, E;
    vector<vector<pair<int,int>>> graph;

    // Step 1: Input
    takeInput(N, E, graph);

    // Step 2: Dijkstra
    vector<int> dist, parent;
    dijkstra(0, graph, dist, parent); // source = 0

    // Step 3: Output
    printResult(N, dist, parent);

    return 0;
}