#include <bits/stdc++.h>
#define int long long
#define ii pair < int , int >
#define fi first
#define se second
using namespace std;
const int N = 105;
int A, B, n, m;
int dist[N];
vector < ii > a[2][105];
struct item
{
int u, cost;
bool ok;
item(int _u = 0, int _cost = 0, bool _ok = 0){
u = _u;
cost = _cost;
ok = _ok;
}
};
struct cmp
{
bool operator()(item a, item b)
{
return a.cost < a.cost;
}
};
priority_queue < item, vector < item >, cmp > q;
void inp()
{
cin >> A >> B;
cin >> n >> m;
for(int i = 1; i <= m; i++){
int u, v, w;
cin >> u >> v >> w;
a[1][u].push_back({v, w});
a[0][v].push_back({u, w});
}
}
int xuly(int x, int w)
{
int tmp = x / 12;
x = x - tmp * 12;
if(x + w == 12){
return 1;
}
if(x + w < 12){
return 2;
}
return 0;
}
void dijk()
{
for(int i = 1; i <= n; i++){
dist[i] = 1e18;
}
dist[A] = 0;
q.push(item(A, 0, 1));
while(!q.empty())
{
int u = q.top().u;
int cost = q.top().cost;
int day = q.top().ok;
q.pop();
if(cost > dist[u]) continue;
for(int i = 0; i < a[day][u].size(); i++){
int v = a[day][u][i].fi;
int w = a[day][u][i].se;
if(dist[v] > dist[u] + w && xuly(dist[u], w) > 0){
if(xuly(dist[u], w) == 1){
dist[v] = dist[u] + w;
q.push(item(v, dist[v], (day + 1) % 2));
}
else{
dist[v] = dist[u] + w;
q.push(item(v, dist[v], day));
}
}
else if(xuly(dist[u], w) == 0){
int tmp = dist[u] / 12;
int x = tmp * 12 + 12 + 12;
q.push(item(v, min(dist[v], x + w), day));
}
if(xuly(dist[u], w) > 0){
// cout << "CCCCCCCCCCCC" << v << "CCCCCCCCC" << '\n';
int tmp = dist[u] / 12;
int x = tmp * 12 + 12;
q.push(item(v, x, (day + 1) % 2));
}
}
}
}
main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
inp();
dijk();
for(int i = 1; i <= n; i++){
cout << "node" << i << " " << dist[i] << '\n';
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgaW50IGxvbmcgbG9uZwojZGVmaW5lIGlpIHBhaXIgPCBpbnQgLCBpbnQgPgojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Ugc2Vjb25kCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IE4gPSAxMDU7CgppbnQgQSwgQiwgbiwgbTsKaW50IGRpc3RbTl07Cgp2ZWN0b3IgPCBpaSA+IGFbMl1bMTA1XTsKCnN0cnVjdCBpdGVtCnsKICAgIGludCB1LCBjb3N0OwogICAgYm9vbCBvazsKICAgIGl0ZW0oaW50IF91ID0gMCwgaW50IF9jb3N0ID0gMCwgYm9vbCBfb2sgPSAwKXsKICAgICAgICB1ID0gX3U7CiAgICAgICAgY29zdCA9IF9jb3N0OwogICAgICAgIG9rID0gX29rOwogICAgfQp9OwoKc3RydWN0IGNtcAp7CiAgICBib29sIG9wZXJhdG9yKCkoaXRlbSBhLCBpdGVtIGIpCiAgICB7CiAgICAgICAgcmV0dXJuIGEuY29zdCA8IGEuY29zdDsKICAgIH0KfTsKCnByaW9yaXR5X3F1ZXVlIDwgaXRlbSwgdmVjdG9yIDwgaXRlbSA+LCBjbXAgPiBxOwoKCnZvaWQgaW5wKCkKewogICAgY2luID4+IEEgPj4gQjsKICAgIGNpbiA+PiBuID4+IG07CiAgICBmb3IoaW50IGkgPSAxOyBpIDw9IG07IGkrKyl7CiAgICAgICAgaW50IHUsIHYsIHc7CiAgICAgICAgY2luID4+IHUgPj4gdiA+PiB3OwogICAgICAgIGFbMV1bdV0ucHVzaF9iYWNrKHt2LCB3fSk7CiAgICAgICAgYVswXVt2XS5wdXNoX2JhY2soe3UsIHd9KTsKICAgIH0KfQoKCmludCB4dWx5KGludCB4LCBpbnQgdykKewogICAgaW50IHRtcCA9IHggLyAxMjsKICAgIHggPSB4IC0gdG1wICogMTI7CiAgICBpZih4ICsgdyA9PSAxMil7CiAgICAgICAgcmV0dXJuIDE7CiAgICB9CiAgICBpZih4ICsgdyA8IDEyKXsKICAgICAgICByZXR1cm4gMjsKICAgIH0KICAgIHJldHVybiAwOwp9CgoKCnZvaWQgZGlqaygpCnsKICAgIGZvcihpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKXsKICAgICAgICBkaXN0W2ldID0gMWUxODsKICAgIH0KICAgIGRpc3RbQV0gPSAwOwogICAgcS5wdXNoKGl0ZW0oQSwgMCwgMSkpOwogICAgd2hpbGUoIXEuZW1wdHkoKSkKICAgIHsKICAgICAgICBpbnQgdSA9IHEudG9wKCkudTsKICAgICAgICBpbnQgY29zdCA9IHEudG9wKCkuY29zdDsKICAgICAgICBpbnQgZGF5ID0gcS50b3AoKS5vazsKICAgICAgICBxLnBvcCgpOwogICAgICAgIGlmKGNvc3QgPiBkaXN0W3VdKSBjb250aW51ZTsKICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgYVtkYXldW3VdLnNpemUoKTsgaSsrKXsKICAgICAgICAgICAgaW50IHYgPSBhW2RheV1bdV1baV0uZmk7CiAgICAgICAgICAgIGludCB3ID0gYVtkYXldW3VdW2ldLnNlOwogICAgICAgICAgICBpZihkaXN0W3ZdID4gZGlzdFt1XSArIHcgJiYgeHVseShkaXN0W3VdLCB3KSA+IDApewogICAgICAgICAgICAgICAgaWYoeHVseShkaXN0W3VdLCB3KSA9PSAxKXsKICAgICAgICAgICAgICAgICAgICBkaXN0W3ZdID0gZGlzdFt1XSArIHc7CiAgICAgICAgICAgICAgICAgICAgcS5wdXNoKGl0ZW0odiwgZGlzdFt2XSwgKGRheSArIDEpICUgMikpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZXsKICAgICAgICAgICAgICAgICAgICBkaXN0W3ZdID0gZGlzdFt1XSArIHc7CiAgICAgICAgICAgICAgICAgICAgcS5wdXNoKGl0ZW0odiwgZGlzdFt2XSwgZGF5KSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZSBpZih4dWx5KGRpc3RbdV0sIHcpID09IDApewogICAgICAgICAgICAgICAgaW50IHRtcCA9IGRpc3RbdV0gLyAxMjsKICAgICAgICAgICAgICAgIGludCB4ID0gdG1wICogMTIgKyAxMiArIDEyOwogICAgICAgICAgICAgICAgcS5wdXNoKGl0ZW0odiwgbWluKGRpc3Rbdl0sIHggKyB3KSwgZGF5KSk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgaWYoeHVseShkaXN0W3VdLCB3KSA+IDApewovLyAgICAgICAgICAgICAgICBjb3V0IDw8ICAiQ0NDQ0NDQ0NDQ0NDIiA8PCB2IDw8ICJDQ0NDQ0NDQ0MiIDw8ICdcbic7CiAgICAgICAgICAgICAgICBpbnQgdG1wID0gZGlzdFt1XSAvIDEyOwogICAgICAgICAgICAgICAgaW50IHggPSB0bXAgKiAxMiArIDEyOwogICAgICAgICAgICAgICAgcS5wdXNoKGl0ZW0odiwgeCwgKGRheSArIDEpICUgMikpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9CgoKCm1haW4oKQp7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOwogICAgY2luLnRpZSgwKTsgY291dC50aWUoMCk7CiAgICBpbnAoKTsKICAgIGRpamsoKTsKICAgIGZvcihpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKXsKICAgICAgICBjb3V0IDw8ICJub2RlIiA8PCBpIDw8ICIgIiA8PCBkaXN0W2ldIDw8ICdcbic7CiAgICB9Cn0K