Bình luận

• 
  

  -2

  vanphukhang_0604    11:25 a.m. 16 Tháng 8, 2023 ← chỉnh sửa 3 →

  CSES - Visiting Cities | Thăm các thành phố

  Bạn muốn đi từ Syrjälä đến Lehmälä bằng máy bay theo tuyến đường có giá tiền nhỏ nhất. Hãy tìm những thành phố mà bạn chắc chắn phải đi qua.

  Input

  • Dòng đầu tiên chứa hai số nguyên \(n \ (1 \leq n \leq 10^5)\) và \(m \ (1 \leq m \leq 2 \cdot 10^5)\): số thành phố và số chuyến bay. Các thành phố được đánh số \(1, 2, \ldots, n\). Thành phố \(1\) là Syrjälä, và thành phố \(n\) là Lehmälä.
  • \(m\) dòng tiếp theo mô tả các chuyến bay. Mỗi dòng ghi ba số nguyên \(a, b \ (1 \leq a, b \leq n)\) và \(c \ (1 \leq c \leq 10^9)\): có một chuyến bay từ thành phố \(a\) đến thành phố \(b\) với giá \(c\). Tất cả các chuyến bay đều là chuyến bay một chiều.
  • Dữ liệu đảm bảo có một tuyến đường từ Syrjälä đến Lehmälä.

  Output

  • Dòng đầu in một số nguyên \(k\): số thành phố chắc chắn nằm trên đường đi.
  • Dòng tiếp theo in \(k\) thành phố trên theo thứ tự tăng dần.

  Example

  Test 1

  Input

  5 6
  1 2 3
  1 3 4
  2 3 1
  2 4 5
  3 4 1
  4 5 8

  Output

  4  
  1 3 4 5