<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

352. Beerland Attacks
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



In this task Berland again needs your help. Berland consists of N cities. Some pairs of the cities are connected by bidirectional roads. Each road is characterized by its length. The cities are numbered from 1 to N, the capital has number 1. From time to time the President of Beerland takes a tour around the country visiting all the cities. The tour is a sequence of trips. The goal of each trip is to visit one of the cities and return to the capital. During the trip the President chooses one of the shortest ways from the capital to the desired city.

Long time ago, when Dijkstra algorithm seemed to be difficult, the royal security service created a secret set of roads T. Security officers created the T set in such a manner that it is possible to get by the shortest way from the capital to any city using only roads from the set T. Moreover, there is only one way from the capital to each city along the roads from the T set. The smartest citizens called this set "tree of the shortest paths".

The President uses only roads from the T set during his trips. With years passing the set lost much of its secrecy. Moreover, recently Beerland extremists have come into possesion of the secret set.

Now the royal security service has the new task. For each city except the capital it is required to find out vi (2≤ i≤ N), where vi is the length of the shortest path to the i-th city if the last road on the way to this city is attacked and the President can't use it any more.

Input
The first line of the input contains two integer numbers N and M (; ), where N is a number of the cities in the country and m is a number of the roads. The following M lines contain the description of the roads, one per line. Each road description is given as the four integer numbers aj, bj, lj, tj, where aj, bj are numbers of the cities connected by the road (1 ≤ aj,bj ≤ n; aj <> bj), lj — length of the road (1 ≤ lj ≤ 105), tj is equal to 1 if the road belongs to the shortest paths tree T and to 0 otherwise.

The given set T satisfies the requirements listed in the problem statement. There can be more than one road between a pair of cities. All roads are bidirectional.

Output
Write to the output N-1 numbers separated by spaces. i-th number should be equal to the length of the shortest way from the capital to the city i+1 or -1 if the way doesn't exist.

Example(s)
sample input
sample output
5 9
3 1 3 1
1 4 2 1
2 1 6 0
2 3 4 0
5 2 3 0
3 2 2 1
5 3 1 1
3 5 2 0
4 5 4 0
6 7 8 5

<|response|>
## 1) Abridged problem statement (concise)

You are given an undirected weighted graph with \(N\) cities and \(M\) roads. City 1 is the capital.  
Some roads are marked \(t=1\); these roads form a **shortest-path tree** \(T\) rooted at city 1: for every city \(v\), the unique path from 1 to \(v\) using only edges of \(T\) is a shortest path in the full graph.

For every city \(v \neq 1\), let \((parent[v], v)\) be the **last tree edge** on the tree path from 1 to \(v\). This edge is “attacked” (removed). Output the length of the shortest path from 1 to \(v\) in the modified graph, or `-1` if unreachable.

---

## 2) Key observations

1. **Tree distances are true shortest distances.**  
   Let \(dist[u]\) be the distance from 1 to \(u\) along the tree \(T\). By definition of \(T\), this equals the shortest distance in the original graph.

2. **Removing \((parent[u],u)\) cuts off the subtree.**  
   Removing that edge disconnects the tree into:
   - subtree \(S_u\): all nodes whose tree path to root goes through \(u\)
   - the rest containing the root

3. **Any reroute must enter the subtree via a non-tree edge.**  
   After the cut, the only remaining way to reach any node in \(S_u\) from the root is to cross from outside \(S_u\) to inside \(S_u\) using at least one **non-tree** edge (\(t=0\)).

4. **An optimal reroute uses at most one non-tree edge.**  
   Take any path from 1 to \(u\) in the modified graph. Consider the **last time** it enters \(S_u\). From that point onward it stays inside \(S_u\), and the best way to reach \(u\) is along tree edges (since tree paths are shortest inside the tree). So we only need one “crossing” non-tree edge.

5. **Reformulate the answer using a value per non-tree edge.**  
   For a non-tree edge \((a,b,w)\), define:
   \[
   val(a,b)=dist[a]+dist[b]+w
   \]
   For node \(u\), the best reroute after cutting \((parent[u],u)\) is:
   \[
   answer[u] = \min_{\text{non-tree }(x,y)\text{ crosses cut of }S_u} val(x,y) - dist[u]
   \]
   If no non-tree edge crosses the cut, answer is `-1`.

6. **Which subtrees does a non-tree edge “cross”? Use LCA + subtree aggregation.**  
   For edge endpoints \(a,b\) with \(c=LCA(a,b)\) in tree \(T\):
   - add \(val\) to node \(a\)
   - add \(val\) to node \(b\)
   - remove \(val\) twice at node \(c\)

   Then, if you aggregate these multisets bottom-up, the multiset stored at node \(u\) contains exactly the \(val\)’s of non-tree edges with **exactly one endpoint in \(S_u\)** (i.e., crossing the cut).

7. **Efficient aggregation via DSU-on-tree (small-to-large).**  
   Each node maintains a multiset of candidate \(val\)’s from its subtree. Merge children’s multisets into the parent, always merging smaller into larger.

---

## 3) Full solution approach

### Step A: Build the tree and compute `parent[]`, `dist[]`
- Read all edges; split into:
  - `tree` edges (t=1) to build adjacency of \(T\)
  - `nontree` edges (t=0) stored separately
- DFS/BFS on the tree from root 1:
  - `parent[v]` = parent in rooted tree
  - `dist[v]` = distance from root along tree

### Step B: Prepare LCA on the tree
We need fast \(LCA(u,v)\) for every non-tree edge. Use:
- Euler tour of tree + RMQ (sparse table) to answer LCA in \(O(1)\)
- Preprocessing \(O(N\log N)\)

### Step C: Create “events” for each non-tree edge
For each undirected non-tree edge \((a,b,w)\):
- \(val = dist[a]+dist[b]+w\)
- \(c=LCA(a,b)\)
- `addv[a].push(val)`, `addv[b].push(val)`
- `remv[c].push(val)` twice

### Step D: DSU-on-tree to compute answer for every node
Postorder DFS on the tree:
- Each node returns a pointer/reference to a multiset representing all active `val` candidates for its subtree.
- Merge children into current (small-to-large).
- Insert all `addv[u]`, erase all `remv[u]` (erase one occurrence each time).
- For \(u \neq 1\):
  - if multiset empty ⇒ `ans[u] = -1`
  - else `ans[u] = minVal - dist[u]`

### Complexity
- LCA preprocessing: \(O(N\log N)\)
- Processing non-tree edges: \(O(M)\) LCAs
- DSU-on-tree merges + multiset ops: about \(O((N+M)\log (N+M))\)
Fits typical constraints for this classical problem.

---

## 4) C++ implementation

```cpp
#include <bits/stdc++.h>
// #include <coding_library/tree/lca_sparse_table.hpp>
// #include <coding_library/data_structures/sparse_table.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

template<class T, T (*merge)(T, T)>
class SparseTable {
  private:
    int n;
    vector<vector<T>> dp;
    vector<int> prec_lg2;

  public:
    SparseTable() {
        n = 0;
        dp.clear();
        prec_lg2.clear();
    }

    void init(const vector<T>& a) {
        n = a.size();
        prec_lg2.resize(n + 1);
        for(int i = 2; i <= n; i++) {
            prec_lg2[i] = prec_lg2[i >> 1] + 1;
        }

        dp.assign(prec_lg2[n] + 1, vector<T>(n));
        dp[0] = a;

        for(int j = 1; (1 << j) <= n; j++) {
            for(int i = 0; i + (1 << j) <= n; i++) {
                dp[j][i] = merge(dp[j - 1][i], dp[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    T query(int l, int r) {
        int k = prec_lg2[r - l + 1];
        return merge(dp[k][l], dp[k][r - (1 << k) + 1]);
    }
};

class LCAUtilsRMQ {
  private:
    static pair<int, int> _min_custom(pair<int, int> a, pair<int, int> b) {
        return min(a, b);
    }

    SparseTable<pair<int, int>, _min_custom> rmq;
    vector<int> pos, dep;
    vector<pair<int, int>> order;

    void pre_dfs(int u, int pr = -1, int d = 0) {
        pos[u] = order.size();
        dep[u] = d;
        order.push_back({d, u});

        for(int v: adj[u]) {
            if(v != pr) {
                pre_dfs(v, u, d + 1);
                order.push_back({d, u});
            }
        }
    }

  public:
    int n;
    vector<vector<int>> adj;

    LCAUtilsRMQ() { n = 0; }
    LCAUtilsRMQ(int _n) { init(_n); }
    LCAUtilsRMQ(int _n, const vector<vector<int>>& _adj) {
        init(_n);
        adj = _adj;
    }

    void add_edge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void init(int _n) {
        n = _n;
        order.clear();
        adj.assign(n, {});
    }

    void prepare(int root = 0) {
        order.clear();
        pos.resize(n);
        dep.resize(n);
        pre_dfs(root);
        rmq.init(order);
    }

    int lca(int u, int v) {
        if(pos[u] > pos[v]) {
            swap(u, v);
        }
        return rmq.query(pos[u], pos[v]).second;
    }

    int dist(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
};

using LcaUtils = LCAUtilsRMQ;

int n, m;
LcaUtils lca;
vector<vector<pair<int, int>>> tree, nontree;
vector<int> parent;
vector<int64_t> dist;
vector<vector<int64_t>> addv, remv;
vector<int64_t> ans;

void dfs0(int u, int p) {
    for(auto [v, w]: tree[u]) {
        if(v == p) {
            continue;
        }
        parent[v] = u;
        dist[v] = dist[u] + w;
        dfs0(v, u);
    }
}

multiset<int64_t>* dfs(int u) {
    multiset<int64_t>* cur = new multiset<int64_t>();

    for(auto [v, w]: tree[u]) {
        if(v == parent[u]) {
            continue;
        }
        multiset<int64_t>* child = dfs(v);
        if(child->size() > cur->size()) {
            swap(cur, child);
        }
        cur->insert(child->begin(), child->end());
        delete child;
    }

    for(int64_t x: addv[u]) {
        cur->insert(x);
    }

    for(int64_t x: remv[u]) {
        auto it = cur->find(x);
        if(it != cur->end()) {
            cur->erase(it);
        }
    }

    if(u != 0) {
        if(cur->empty()) {
            ans[u] = -1;
        } else {
            ans[u] = *cur->begin() - dist[u];
        }
    }

    return cur;
}

void read() {
    cin >> n >> m;
    tree.assign(n, {});
    nontree.assign(n, {});
    addv.assign(n, {});
    remv.assign(n, {});
    dist.assign(n, 0);
    parent.assign(n, -1);
    ans.assign(n, -1);
    lca.init(n);

    for(int i = 0; i < m; i++) {
        int a, b, w, t;
        cin >> a >> b >> w >> t;
        a--;
        b--;
        if(t) {
            tree[a].push_back({b, w});
            tree[b].push_back({a, w});
            lca.add_edge(a, b);
        } else {
            nontree[a].push_back({b, w});
            nontree[b].push_back({a, w});
        }
    }
}

void solve() {
    // The core observation in this problem is that due to the fact that this is
    // a Dijkstra tree, after we burn some edge, we need to use at most one
    // non-special edge. This can be shown with a simple contradiction (assume
    // we use 2 non-special edges, consider the latest one in the path, and
    // then pick the simpler path going along the original tree edges which is
    // at least as quick). This means that if we burn the edge (par[u], u), we
    // want to choose some non-special edge (x, y, w) that minimizes dist(u, x)
    // + dist(1, y) + w, with x in the subtree of u and y outside of the tree.
    //
    // The naive way to do this is in O(N*M) by passing through all edges, but
    // this will be too slow. Instead we can do something smarter with small to
    // large trick. Let's have events - for edge (x, y, w), we will add this
    // event at x, add it at y, and remove it twice at lca(x, y). Each event is
    // represented by a single value equal to w + dist[x] + dist[y] where
    // dist[.] is the distance from the root. Then when we are finding the
    // answer for some u, we want to get min(events_subtree) - dist[u]. This can
    // easily be done with small to large, and the complexity will be somewhat
    // lower at O((N+M) log^2 (N+M)).

    dfs0(0, -1);
    lca.prepare(0);

    for(int u = 0; u < n; u++) {
        for(auto [v, w]: nontree[u]) {
            if(u < v) {
                int64_t val = dist[u] + dist[v] + w;
                int c = lca.lca(u, v);
                addv[u].push_back(val);
                addv[v].push_back(val);
                remv[c].push_back(val);
                remv[c].push_back(val);
            }
        }
    }

    dfs(0);

    for(int i = 1; i < n; i++) {
        cout << ans[i];
        if(i < n - 1) {
            cout << " ";
        }
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

Python needs care: we need a “multiset with get-min” and efficient small-to-large merging.  
Below uses `Counter + heap` with lazy deletions, and merges counters small-to-large.

```python
import sys
sys.setrecursionlimit(1_000_000)

import heapq
from collections import Counter

# -------- LCA via Euler tour + Sparse Table (RMQ) --------

class LCA_RMQ:
    def __init__(self, n):
        self.n = n
        self.adj = [[] for _ in range(n)]
        self.euler = []
        self.first = [-1] * n
        self.depth = [0] * n
        self.log = []
        self.st = []

    def add_edge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)

    def _dfs(self, u, p, d):
        self.first[u] = len(self.euler)
        self.depth[u] = d
        self.euler.append((d, u))
        for v in self.adj[u]:
            if v == p:
                continue
            self._dfs(v, u, d + 1)
            self.euler.append((d, u))

    def prepare(self, root=0):
        self.euler = []
        self._dfs(root, -1, 0)
        m = len(self.euler)

        self.log = [0] * (m + 1)
        for i in range(2, m + 1):
            self.log[i] = self.log[i // 2] + 1

        kmax = self.log[m]
        self.st = [self.euler[:]]
        j = 1
        while (1 << j) <= m:
            prev = self.st[j - 1]
            half = 1 << (j - 1)
            curr = []
            # RMQ for minimum (depth, node)
            for i in range(0, m - (1 << j) + 1):
                a = prev[i]
                b = prev[i + half]
                curr.append(a if a < b else b)
            self.st.append(curr)
            j += 1

    def lca(self, u, v):
        a, b = self.first[u], self.first[v]
        if a > b:
            a, b = b, a
        length = b - a + 1
        k = self.log[length]
        left = self.st[k][a]
        right = self.st[k][b - (1 << k) + 1]
        return left[1] if left < right else right[1]

# -------- Multiset with min + merge (small-to-large) --------

class MultiSetMin:
    """
    Multiset supporting:
      - add(x)
      - discard_one(x) (if exists)
      - get_min() (returns minimum element or None)
      - merge_from(other): merges other's counts into self
    Implementation: Counter + min-heap (lazy deletion).
    """
    __slots__ = ("cnt", "heap", "size")

    def __init__(self):
        self.cnt = Counter()
        self.heap = []
        self.size = 0

    def add(self, x):
        self.cnt[x] += 1
        heapq.heappush(self.heap, x)
        self.size += 1

    def discard_one(self, x):
        if self.cnt[x] > 0:
            self.cnt[x] -= 1
            self.size -= 1

    def get_min(self):
        while self.heap and self.cnt[self.heap[0]] == 0:
            heapq.heappop(self.heap)
        return self.heap[0] if self.heap else None

    def merge_from(self, other):
        # merge other's counter into self (assume self is bigger)
        for x, c in other.cnt.items():
            if c:
                self.cnt[x] += c
                self.size += c
                # push once; heap + counter will still work
                heapq.heappush(self.heap, x)

# -------- Main solve --------

def solve():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    m = int(next(it))

    tree = [[] for _ in range(n)]      # t=1 edges: (v, w)
    nontree = [[] for _ in range(n)]   # t=0 edges: (v, w)
    lca = LCA_RMQ(n)

    for _ in range(m):
        a = int(next(it)) - 1
        b = int(next(it)) - 1
        w = int(next(it))
        t = int(next(it))
        if t == 1:
            tree[a].append((b, w))
            tree[b].append((a, w))
            lca.add_edge(a, b)
        else:
            nontree[a].append((b, w))
            nontree[b].append((a, w))

    # parent/dist on the tree
    parent = [-1] * n
    dist = [0] * n
    stack = [(0, -1)]
    order = []
    while stack:
        u, p = stack.pop()
        parent[u] = p
        order.append(u)
        for v, w in tree[u]:
            if v == p:
                continue
            dist[v] = dist[u] + w
            stack.append((v, u))

    lca.prepare(0)

    addv = [[] for _ in range(n)]
    remv = [[] for _ in range(n)]

    # process each undirected non-tree edge once (u < v)
    for u in range(n):
        for v, w in nontree[u]:
            if u < v:
                val = dist[u] + dist[v] + w
                c = lca.lca(u, v)
                addv[u].append(val)
                addv[v].append(val)
                remv[c].append(val)
                remv[c].append(val)

    ans = [-1] * n

    sys.setrecursionlimit(1_000_000)

    def dfs(u):
        cur = MultiSetMin()

        # merge children
        for v, _w in tree[u]:
            if v == parent[u]:
                continue
            child = dfs(v)
            if child.size > cur.size:
                cur, child = child, cur
            cur.merge_from(child)

        # apply events
        for x in addv[u]:
            cur.add(x)
        for x in remv[u]:
            cur.discard_one(x)

        if u != 0:
            mn = cur.get_min()
            ans[u] = -1 if mn is None else (mn - dist[u])
        return cur

    dfs(0)

    # output for nodes 2..N
    sys.stdout.write(" ".join(str(ans[i]) for i in range(1, n)) + "\n")

if __name__ == "__main__":
    solve()
```
