#include "cyberland.h"
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define ld double
#define maxn 100005
#define ff first
#define ss second
#define pii pair<ll, ll>
const ld inf = 1e15;
const ld eps = 1e-10;
vector<pii> adj[maxn];
int type[maxn];
ld d[maxn], d2[maxn];
void dijkstra(int n) {
priority_queue<pair<ld, int> , vector<pair<ld, int> >, greater<pair<ld, int> > > pq;
for (int i = 0;i < n;i++) {
d2[i] = d[i];
pq.push(make_pair(d[i], i));
}
while (pq.size()) {
auto [dis, cur] = pq.top();pq.pop();
if (abs(dis - d[cur]) > eps) continue;
for (auto [v, w]:adj[cur]) {
if (type[v] == 0 && d[v] > 0) {
d[v] = 0;
pq.push(make_pair(0, v));
}
if (d[cur] + w < d[v]) {
d[v] = d[cur]+w;
pq.push(make_pair(d[v], v));
}
if (type[v] == 2 && (d[cur] + w) / 2 < d2[v]) {
d2[v] = (d[cur] + w) / 2;
}
}
}
pary(d, d + n);
pary(d2, d2+n);
}
double solve(int N, int M, int K, int H, vector<int> U, vector<int> V, vector<int> W, vector<int> arr) {
for (int i = 0;i < N;i++) {
adj[i].clear();
d[i] = d2[i] = inf;
type[i] = arr[i];
}
for (int i = 0;i < M;i++) {
if (U[i] == H) swap(U[i], V[i]);
adj[U[i]].push_back({V[i], W[i]});
if (V[i] != H) adj[V[i]].push_back({U[i], W[i]});
}
d[0] = d2[0] = 0;
for (int i = 0;i <= min(K, 100);i++) {
dijkstra(N);
if (i < K) {
for (int j = 0;j < N;j++) {
d[j] = min(d[j], d2[j]);
}
}
}
if (d[H] == inf) {
return -1;
}
return d[H];
}
