| 199 | } |
| 200 | |
| 201 | public static void main(String[] args) throws Exception { |
| 202 | FastReader in = new FastReader(System.in); |
| 203 | PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); |
| 204 | n = in.nextInt(); |
| 205 | m = in.nextInt(); |
| 206 | s = in.nextInt(); |
| 207 | cntt = n; |
| 208 | for (int i = 1; i <= n; i++) { |
| 209 | father[i] = i; |
| 210 | } |
| 211 | for (int i = 1, op, a, b, c, d, w, u, v; i <= m; i++) { |
| 212 | op = in.nextInt(); |
| 213 | if (op == 1) { |
| 214 | a = in.nextInt(); |
| 215 | b = in.nextInt(); |
| 216 | c = in.nextInt(); |
| 217 | d = in.nextInt(); |
| 218 | w = in.nextInt(); |
| 219 | if (find(a) == find(b) && find(c) == find(d)) { |
| 220 | u1[++cntq] = a; |
| 221 | v1[cntq] = b; |
| 222 | u2[cntq] = c; |
| 223 | v2[cntq] = d; |
| 224 | weight[cntq] = w; |
| 225 | } |
| 226 | } else { |
| 227 | u = in.nextInt(); |
| 228 | v = in.nextInt(); |
| 229 | w = in.nextInt(); |
| 230 | int ufa = find(u); |
| 231 | int vfa = find(v); |
| 232 | if (ufa != vfa) { |
| 233 | addEdge1(u, v); |
| 234 | addEdge1(v, u); |
| 235 | addEdge2(u, v, w); |
| 236 | addEdge2(v, u, w); |
| 237 | father[ufa] = vfa; |
| 238 | } |
| 239 | } |
| 240 | } |
| 241 | for (int i = 1; i <= n; i++) { |
| 242 | if (dep[i] == 0) { |
| 243 | build(i, i); |
| 244 | } |
| 245 | } |
| 246 | for (int i = 1; i <= cntq; i++) { |
| 247 | pathToPath(u1[i], v1[i], u2[i], v2[i], weight[i]); |
| 248 | } |
| 249 | dijkstra(); |
| 250 | for (int i = 1; i <= n; i++) { |
| 251 | out.print(dist[i] == INF ? -1 : dist[i]); |
| 252 | out.print(" "); |
| 253 | } |
| 254 | out.flush(); |
| 255 | out.close(); |
| 256 | } |
| 257 | |
| 258 | // 读写工具类 |