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.|

CENTRE28 - CENTRE

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/centre28


Theo thống kê cho biết mức độ tăng trưởng kinh tế của nước Peace trong năm 2006 rất đáng khả quan. Cả nước có tổng cộng N thành phố lớn nhỏ được đánh số tuần tự từ 1 đến N phát triển khá đồng đều. Giữa N thành phố này là một mạng lưới gồm M đường đi hai chiều, mỗi tuyến đường nối 2 trong N thành phố sao cho không có 2 thành phố nào được nối bởi quá 1 tuyến đường. Trong N thành phố này thì thành phố 1 và thành phố N là 2 trung tâm kinh tế lớn nhất nước và hệ thống đường đảm bảo luôn có ít nhất một cách đi từ thành phố 1 đến thành phố N.

Tuy nhiên,cả 2 trung tâm này đều có dấu hiệu quá tải về mật độ dân số. Vì vậy, đức vua Peaceful quyết định chọn ra thêm một thành phố nữa để đầu tư thành một trung tâm kinh tế thứ ba. Thành phố này sẽ tạm ngưng mọi hoạt động thường nhật, cũng như mọi luồng lưu thông ra vào để tiến hành nâng cấp cơ sở hạ tầng. Nhưng trong thời gian sửa chữa ấy, phải bảo đảm đường đi ngắn nhất từ thành phố 1 đến thành phố N không bị thay đổi, nếu không nền kinh tế quốc gia sẽ bị trì trệ.

Vị trí và đường nối giữa N thành phố được mô tả như một đồ thị N đỉnh M cạnh. Hãy giúp nhà vua đếm số lượng thành phố có thể chọn làm trung tâm kinh tế thứ ba sao cho thành phố được chọn thỏa mãn các điều kiện ở trên

Input

Dòng đầu tiên ghi 2 số nguyên dương N và M là số thành phố và số tuyến đường.

Dòng thứ i trong số M dòng tiếp theo ghi 3 số nguyên dương xi, yi và di với ý nghĩa tuyến đường thứ i có độ dài di và nối giữa 2 thành phố xi, yi.

Output

Dòng đầu tiên ghi số tự nhiên S là số lượng các thành phố có thể chọn làm trung tâm kinh tế thứ ba.

S dòng tiếp theo, mỗi dòng ghi 1 số nguyên dương là số thứ tự của thành phố được chọn ( In ra theo thứ tự tăng dần )

Example

Input:
6 6
1 2 1
2 3 1
3 6 1
1 4 100
4 5 100
5 6 100

Output:
2
4 
5

Giới hạn

  • 2 ≤ N ≤ 30000
  • 1 ≤ M ≤ 100000
  • 1 ≤ di ≤ 1000

Được gửi lên bởi:special_one
Ngày:2008-05-25
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:IOICAMP4

hide comments
2015-06-10 16:56:34
dijkstra heap 20đ.......không biết có test hiểm hk nữa
@@
2015-06-01 07:06:46 [Nghien] Le Long
Dijkstra thường AC =))
2015-05-17 06:49:19 Do Hong Huan
Bài này không tăng giới hạn gì hết, ai 70 thì xem lại giới hạn của d đi.
2015-04-30 18:43:19 even when you try to hurt me...
k cần tăng giới hạn đâu nhé
2014-08-11 16:17:03 Thcs Ðặng Chánh Kỷ
sửa < thành <> là ac ngay ấy mà, dijkstra heap thôi, có qhd đâu
2014-08-10 18:49:13 Thcs Ðặng Chánh Kỷ
tự nghĩ đi bạn ơi, thế mới lên được chơ
2014-08-04 03:21:55 Kraken
dijkstra heap à?
2014-08-02 16:37:46 Lollipop
sao toàn 60 thế, sai đâu nhỉ :(
2014-08-02 07:51:00 Nắng
đúng là bài này có test n>30000, tăng giới hạn lên mới AC @@ các bạn cẩn thận :D
2014-07-09 04:51:54 Lưu Vịnh
Bài này đổi giới hạn lại 300000 là ko bị tràn mảng :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.