Tính phí đường bộ

Vương quốc Byteland có $N$ nút giao thông trọng điểm được đánh số từ $1$ đến $N$. Hệ thống đường cao tốc gồm $M$ con đường hai chiều đảm bảo đi lại giữa các nút giao thông với nhau, các con đường được đánh số từ $1$ đến $M$. Con đường thứ $i$ nối nút giao thông $X_i$ với $Y_i$ $(1\le i\le M;1\le X_i,Y_i\le N)$ có phí đường bộ là $Z_i$ $(Z_i\le {10}^6)$.

Ví dụ: với $4$ nút giao thông và $4$ con đường $1-2$ (phí $10$), $1-3$ (phí $30$), $2-4$ (phí $20$), $3-4$ (phí $5$), từ nút giao thông $1$ đến nút giao thông $4$ có hai đường đi khác nhau: đường đi thứ nhất là $1\to 2\to 4$ có tổng phí đường bộ là $30$, đường đi thứ hai là $1\to 3\to 4$ có tổng phí đường bộ là $35$.

Để giảm chi phí đi lại góp phần thúc đẩy phát triển kinh tế giữa các vùng, Quốc vương đã ban hành chính sách mới cho phép người dân đăng kí miễn phí tối đa $K$ con đường bất kì trên hành trình của mình.

Yêu cầu: Hãy lập trình tính tổng phí đường bộ nhỏ nhất khi đi từ nút giao thông $S$ đến nút giao thông $T$ sau khi được Quốc vương ban hành chính sách mới.

Dữ liệu vào

• Dòng đầu ghi năm số nguyên $N,M,K,S,T$;
• Dòng thứ $i$ trong $M$ dòng tiếp theo ghi ba số nguyên dương $X_i,Y_i,Z_i$.

Các số cách nhau ít nhất một dấu cách.

Dữ liệu ra

In ra một số nguyên duy nhất là tổng phí đường bộ nhỏ nhất tìm được.

Ràng buộc

• $2\le N\le 100000$, $1\le M\le 100000$, $0\le K\le 10$
• $1\le S,T\le N$
• $1\le X_i,Y_i\le N$, $1\le Z_i\le {10}^6$
• Từ mỗi nút giao thông có thể đi đến mọi nút giao thông khác.

Subtasks

• Subtask 1 ($20\%$ số điểm): $1<N,M\le 100000$ và $K=0$.
• Subtask 2 ($20\%$ số điểm): $1<N\le 100$, $M\le 1000$ và $K=1$.
• Subtask 3 ($20\%$ số điểm): $1<N,M\le 100000$ và $K=1$.
• Subtask 4 ($40\%$ số điểm): $100<N,M\le 100000$ và $1<K\le 10$.

Ví dụ