Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P18QPROG - QUALIFY ROUND 2018 G - ĐIỂM HẸN

Ngày trở về quê hương, Tí rất muốn gặp mặt các bạn cũ của mình. Tại quê nhà, Tí có N người bạn, mỗi bạn lại sống ở một thị trấn khác nhau trong thành phố. Có M tuyến đường kết nối các thị trấn này với nhau. Tí muốn chọn một địa điểm gặp mặt tối ưu (điểm P) trên tuyến đường thứ K, sao cho giá trị lớn nhất độ dài quãng đường cần phải di chuyển của N bạn tới điểm P là nhỏ nhất.

Các bạn hãy giúp Tí tìm điểm P tối ưu nhất.

Input

Dòng đầu tiên là số lượng bộ test T (T ≤ 10).

Mỗi test bắt đầu bởi 3 số nguyên N, M và K (2 ≤ N, M ≤ 100 000).

M dòng tiếp theo, mỗi dòng gồm 3 số nguyên u, v, c (c ≤ 10^9) cho biết có một tuyến đường 2 chiều kết nối thành phố u và v.

Input đảm bảo đơn đồ thị và không có tuyến đường nào tự kết nối thị trấn nào đó.

Output

Với mỗi test, in ra hai số thực X và Y với 5 chữ số sau dấu phảy, với X là khoảng cách giữa P và A, còn Y là giá trị lớn nhất của các đường đi ngắn nhất từ P tới các thị trấn 1, 2, …, N.

Thứ tự u, v của mỗi tuyến đường được giữ nguyên. Giả sử điểm P cần tìm kết nối thị trấn A và B. Khoảng cách giữa P và A bằng 8, P và B bằng 2, bạn phải in ra 8.

Nếu có nhiều đáp án, hãy tìm điểm P gần A nhất.

Example

Input:
2
2 1 1
1 2 10
4 4 1
1 2 10
2 3 10
3 4 1
4 1 5 Output: 5.00000 5.00000
2.00000 8.00000

Giải thích test 2: Điểm hẹn P nằm giữa thị trấn của hai bạn 1 và 2, cách thị trấn 1 khoảng cách bằng 2.
Khoảng cách bạn 1 phải di chuyển là 2.
Khoảng cách bạn 2 phải di chuyển là 8.
Khoảng cách bạn 3 phải di chuyển là 8.
Khoảng cách bạn 4 phải di chuyển là 7.


Được gửi lên bởi:adm
Ngày:2018-05-14
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.