Bạn được cung cấp một mạng lưới giao thông gồm \(N\) trạm và \(M\) con đường một chiều nối giữa chúng, trong đó có rất nhiều đoạn dốc mang trọng số âm (tiết kiệm năng lượng).

Hãy tìm lượng năng lượng tích lũy tối thiểu cần thiết để đi từ trạm nguồn \(S\) đến tất cả các trạm khác trên đồ thị. Hệ thống kiểm thử chứa các bộ dữ liệu đồ thị dạng lưới đặc biệt được thiết kế để đưa thuật toán hàng đợi SPFA cơ bản rơi vào trạng thái tệ nhất và dẫn tới giới hạn thời gian (TLE). Thí sinh cần áp dụng kỹ thuật tối ưu hóa hàng đợi song hướng SLF (Small Label First) để tối ưu thời gian thực thi.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên \(N, M\) và \(S\) (\(1 \le N \le 1000\), \(1 \le M \le 5000\), \(1 \le S \le N\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\) (\(1 \le u, v \le N\), \(-1000 \le w \le 1000\)) mô tả một con đường một chiều đi từ \(u\) đến \(v\) có chi phí \(w\).

Kết quả ra

• In ra \(N\) số nguyên trên một dòng, số thứ \(i\) là lượng chi phí nhỏ nhất từ \(S\) đến địa điểm \(i\). Nếu không thể đi tới, in ra \(-1\).

Ví dụ

Input

4 4 1
1 2 -5
2 3 2
3 4 -1
1 3 -2

Output

0 -5 -3 -4