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

// INF = very large value (used as initial distance)
const int INF = 1e9;

// -------- GLOBAL VARIABLES ---------

// graph[u] = list of (neighbor, weight)
vector<vector<pair<int,int>>> graph;

// dist[i] = shortest distance from source (0) to node i
vector<int> dist;

// parent[i] = previous node of i (for path tracking)
vector<int> parent;

// color[i] = state of node
// -1 = unvisited, 0 = processing, 1 = visited
vector<int> color;


// ------- FUNCTION DECLARATIONS --------
void takeInput(int e);
void dijkstra(int source, int n);
void printPath(int node);
void printResult(int n);


// -------- MAIN FUNCTION ---------
int main() {
    int nodes, edges;

    // input number of nodes and edges
    cin >> nodes >> edges;

    // resize all global vectors
    graph.resize(nodes + 1);
    dist.resize(nodes + 1);
    parent.resize(nodes + 1);
    color.resize(nodes + 1);

    takeInput(edges);       // input graph
    dijkstra(0, nodes);    // run Dijkstra from source node 0
    printResult(nodes);    // print result

    return 0;
}


// ------ INPUT FUNCTION -------
void takeInput(int e) {
    int u, v, wt;

    // read all edges
    for (int i = 0; i < e; i++) {
        cin >> u >> v >> wt;

        // store graph (undirected)
        graph[u].push_back({v, wt});
        graph[v].push_back({u, wt});
    }
}


// ------- DIJKSTRA ALGORITHM --------
void dijkstra(int source, int n) {

    // min-heap (priority queue)
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

    // initialize all nodes
    for (int i = 0; i <= n; i++) {
        dist[i] = INF;      // initially distance = infinity
        parent[i] = -1;     // no parent
        color[i] = -1;      // unvisited
    }

    // start from source
    dist[source] = 0;
    pq.push({0, source});
    color[source] = 0; // processing

    // main loop
    while (!pq.empty()) {

        int u = pq.top().second;
        pq.pop();

        // if already visited, skip
        if (color[u] == 1) continue;

        color[u] = 1; // mark visited

        // check all neighbors of u
        for (auto edge : graph[u]) {
            int v = edge.first;
            int wt = edge.second;

            // if neighbor not visited before
            if (color[v] == -1) {
                color[v] = 0; // mark as processing
            }

            // relaxation step (main Dijkstra logic)
            if (dist[u] + wt < dist[v]) {
                dist[v] = dist[u] + wt; // update distance
                parent[v] = u;          // store parent for path
                pq.push({dist[v], v});
            }
        }
    }
}


// ------ PRINT PATH --------
// Recursively prints path from source (0) to node
void printPath(int node) {

    if (node == -1) return;

    // first print parent path
    if (parent[node] != -1) {
        printPath(parent[node]);
        cout << " → ";
    }

    // then print current node
    cout << node;
}


// ------ PRINT RESULT --------
void printResult(int n) {

    for (int i = 1; i <= n; i++) {

        cout << "Customer " << i << ": ";

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