Bessla Motors

Nong dan John muon xac dinh cac diem den co ket noi tot voi mang luoi tram sac Bessla. Co $N$ diem, trong do $C$ diem dau tien la tram sac, cac diem con lai la diem den. Cac diem duoc noi boi $M$ con duong hai chieu, moi duong co do dai ${\ell }_i$. Xe Bessla co the di toi da $R$ dam tu mot tram sac.

Mot diem den duoc goi la "ket noi tot" neu co the di den tu it nhat $K$ tram sac khac nhau (moi lan xuat phat tu tram voi binh day).

Hay dem so diem den ket noi tot va liet ke chung.

Du lieu vao

• Dong 1: Nam so nguyen $N$, $M$, $C$, $R$, $K$.
• $M$ dong tiep theo: Ba so nguyen $u_i$, $v_i$, ${\ell }_i$ -- duong noi $u_i$ va $v_i$ voi do dai ${\ell }_i$.

Du lieu ra

• Dong 1: So luong diem den ket noi tot.
• Cac dong tiep theo: Chi so cac diem den (tang dan).

Rang buoc

• $2\le N\le 50000$
• $1\le M\le 100000$
• $1\le C<N$
• $1\le R,{\ell }_i\le {10}^9$
• $1\le K\le 10$

Vi du