function heapMoveUp(hArr, indMap, distance, n) {
    let ind = indMap[n];
    while (ind > 0) {
        const p = ind - 1 >> 1;
        if (distance[hArr[p]] > distance[hArr[ind]]) { // comparison
            [hArr[p], hArr[ind]] = [hArr[ind], hArr[p]];
            indMap[hArr[p]] = p;
            indMap[hArr[ind]] = ind;
            ind = p;
        } else {
            break;
        }
    }
}
function heapMoveDown(hArr, indMap, distance, hSize, n) {
    let ind = indMap[n];
    while (ind < hSize) {
        let c = 2 * ind + 1;
        if (c >= hSize) break;

        const s = c + 1;
        if (s < hSize && distance[hArr[c]] > distance[hArr[s]]) { // comparison
            c = s;
        }

        if (distance[hArr[ind]] <= distance[hArr[c]]) break; // comparison

        [hArr[ind], hArr[c]] = [hArr[c], hArr[ind]];
        indMap[hArr[ind]] = ind;
        indMap[hArr[c]] = c;
        ind = c;
    }
}

function shortestReach(n, edges, s) {
    const graph = {};
    for (let i = 1; i <= n; i++) {
        graph[i] = {};
    }
    for (const [begin, end, weight] of edges) {
        if ((graph[begin][end] ?? Infinity) < weight) continue;
        graph[begin][end] = weight;
        graph[end][begin] = weight;
    }

    const result = {};
    const distance = { [s]: 0 };
    const indMap = {};
    const hArr = [];
    let hSize = 0;
    function insertHeap(n) {
        const ind = hSize;
        hArr[hSize++] = n;
        indMap[n] = ind;
        heapMoveUp(hArr, indMap, distance, n);
    }
    function deleteHeap() {
        const ret = hArr[0];
        hArr[0] = hArr[--hSize];
        delete indMap[ret];
        indMap[hArr[0]] = 0;
        heapMoveDown(hArr, indMap, distance, hSize, hArr[0]);
        return ret;
    }
    insertHeap(s);

    while (hSize > 0) {
        const nextShortest = deleteHeap();
        const minDis = distance[nextShortest];
        result[nextShortest] = minDis;

        for (const [node, weight] of Object.entries(graph[nextShortest])) {
            if (result[node] !== undefined) continue;

            const isInsert = distance[node] === undefined;
            const nDis = minDis + weight;
            if (isInsert) {
                distance[node] = nDis;
                insertHeap(node);
            } else if (distance[node] > nDis) {
                distance[node] = nDis;
                heapMoveUp(hArr, indMap, distance, node);
            }
        }
    }

    const ret = [];
    for (let i = 1; i <= n; i++) {
        if (i === s) continue;
        ret.push(result[i] ?? -1);
    }
    return ret;
}