Trò chơi

Bạn đang chơi trò chơi "Chiến dịch tập kích" với bản đồ gồm $N$ thành phố (đánh số từ $1$ đến $N$) được nối bởi $M$ con đường một chiều. Để đi hết con đường thứ $i$ cần tốn $w_i$ đơn vị thời gian. Bạn xuất phát vào thời điểm $0$ tại thành phố $1$ và cần phá hủy mục tiêu được đặt ở thành phố $N$.

Có một số thành phố được bảo vệ bởi lá chắn phòng thủ. Lá chắn phòng thủ của một thành phố được duy trì bởi một số trạm phát đặt tại những thành phố khác. Muốn tiến vào một thành phố có lá chắn phòng thủ, trước hết phải phá hủy toàn bộ các trạm phát duy trì lá chắn đó; mà muốn phá một trạm phát thì phải tiến được vào thành phố chứa trạm phát ấy.

Bạn có vô số robot cảm tử. Mỗi khi tiến vào một thành phố, một robot lập tức phá hủy một mục tiêu tại đó (phá hủy một trạm phát hoặc mục tiêu ở thành phố $N$). Việc phá hủy không tốn thời gian; chỉ việc di chuyển trên các con đường mới tốn thời gian.

Hãy tính thời gian ít nhất để phá hủy được mục tiêu ở thành phố $N$.

Dữ liệu vào

• Dòng đầu gồm hai số nguyên $N$ và $M$ $(1\le N\le {10}^5,1\le M\le 3·{10}^5)$;
• $M$ dòng tiếp theo, mỗi dòng gồm ba số nguyên $u_i,v_i,w_i$ $(1\le w_i\le {10}^8)$ mô tả một con đường một chiều đi từ thành phố $u_i$ tới thành phố $v_i$ tốn $w_i$ đơn vị thời gian;
• $N$ dòng tiếp theo, dòng thứ $v$ mô tả thành phố $v$: bắt đầu bằng số nguyên $l_v$ là số trạm phát duy trì lá chắn của thành phố $v$, tiếp theo là $l_v$ số hiệu thành phố cho biết vị trí đặt mỗi trạm phát. Nếu $l_v=0$ thì thành phố $v$ không có lá chắn (thành phố $1$ bảo đảm không có lá chắn, tức $l_1=0$).

Dữ liệu bảo đảm luôn có phương án phá hủy mục tiêu và không có trạm phát duy trì lá chắn của một thành phố nào lại nằm trong chính thành phố đó. Có thể có nhiều con đường nối cùng một cặp thành phố và có thể có đường đi từ một thành phố tới chính nó.

Dữ liệu ra

Một số nguyên duy nhất là thời gian ít nhất để phá hủy được mục tiêu ở thành phố $N$.

Ràng buộc

• $1\le N\le {10}^5$, $1\le M\le 3·{10}^5$.
• $1\le u_i,v_i\le N$, $1\le w_i\le {10}^8$.
• $l_1=0$; các trạm phát của thành phố $v$ nằm ở các thành phố khác $v$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $N\le 80$.
• Subtask 2 ($35\%$ số điểm): $N\le 5000$.
• Subtask 3 ($45\%$ số điểm): Không có giới hạn gì thêm.

Ví dụ