Angry Cows

Τα τελευταία χρόνια παρατηρήθηκε ραγδαία εξάπλωση της Νόσου των Εξαιρετικά Κράσινων Βοδιών (Extremely Green Oxen Illness ή EGOI), η οποία είναι μια ασθένεια που καθιστά τις αγελάδες επικίνδυνες για τους πεζοπόρους. Μετά από αρκετά περιστατικά αποφασίστηκε ότι πρέπει να διαχωρίσουμε τις περιοχές όπου βόσκουν οι αγελάδες από το τμήμα των Άλπεων όπου οι άνθρωποι θέλουν να κάνουν πεζοπορία.

Σας δίνεται ένας χάρτης των Άλπεων. Στο χάρτη υπάρχουν ~n~ περιοχές. Κάθε μία από αυτές μπορεί να είναι είτε μια περιοχή που κατοικείται από αγελάδες, είτε μια περιοχή πεζοπορίας, είτε μια αχρησιμοποίητη περιοχή. Ορισμένα ζεύγη περιοχών συνδέονται με αμφίδρομα μονοπάτια. Κάθε μονοπάτι έχει μη αρνητικό μήκος. (Σε όρους θεωρίας γράφων, ο χάρτης είναι ένας μη κατευθυνόμενος γράφος με σταθμισμένες ακμές).

Μπορείτε να χτίσετε τοίχους σε ορισμένες από τις περιοχές.

Μόλις χτίσετε έναν τοίχο σε μια περιοχή, η περιοχή γίνεται απρόσιτη για τους πεζοπόρους και τις αγελάδες - δεν θα μπορούν πλέον να περπατήσουν μέσα από μια τέτοια περιοχή.

Το καθήκον σας είναι να επιλέξετε το σύνολο των περιοχών όπου θα τοποθετηθούν οι τοίχοι. Αυτό το σύνολο περιοχών πρέπει να πληροί τις ακόλουθες προϋποθέσεις:

• Πρέπει να αποτελείται μόνο από αχρησιμοποίητες περιοχές.
• Πρέπει να διαχωρίζει τις περιοχές που κατοικούνται από αγελάδες από τις περιοχές πεζοπορίας. Δηλαδή, μια αγελάδα δεν θα πρέπει πλέον να μπορεί να περπατήσει κατά μήκος μονοπατιών από μια περιοχή που κατοικείται από αγελάδες σε μια περιοχή πεζοπορίας (χωρίς να περάσει από μια περιοχή με τοίχο).
• Δεν πρέπει να διαχωρίζει περιοχές πεζοπορίας μεταξύ τους. Δηλαδή, ένας πεζοπόρος θα πρέπει να εξακολουθεί να μπορεί να περπατά κατά μήκος μονοπατιών από οποιαδήποτε περιοχή πεζοπορίας σε οποιαδήποτε άλλη περιοχή πεζοπορίας (χωρίς να να περάσει από περιοχή με τοίχο).

Εάν υπάρχουν πολλαπλοί τρόποι για την επίτευξη του παραπάνω στόχου, θα μας ενδιαφέρει η ευκολία συντήρησης των τοίχων. Οι τοίχοι θα συντηρούνται από εξειδικευμένα συνεργεία. Υπάρχει ένα τέτοιο συνεργείο με έδρα κάθε περιοχή πεζοπορίας.

Για κάθε περιοχή ~A~ ορίζουμε την απόστασή της ως το ελάχιστο μήκος μιας διαδρομής των μονοπατιών μεταξύ της ~A~ και κάποιας περιοχής πεζοπορίας. (Το μήκος ενός μονοπατιού είναι το άθροισμα των μηκών των μονοπατιών του. Σημειώστε ότι αυτά τα μονοπάτια μπορεί να περνούν μέσα από τοίχους και περιοχές που κατοικούνται από αγελάδες - το συνεργείο συντήρησης τοίχων έχει όλες τις δεξιότητες και τον εξοπλισμό που απαιτούνται για να το κάνει αυτό).

Η απόσταση ενός συνόλου περιοχών είναι τότε η μέγιστη απόσταση οποιασδήποτε περιοχής σε αυτό το σύνολο.

Μεταξύ όλων των συνόλων περιοχών με τοίχους που έχουν τις απαιτούμενες ιδιότητες, βρείτε και επιστρέψτε ένα με τη μικρότερη δυνατή απόσταση. Εάν υπάρχουν πολλά τέτοια σύνολα περιοχών, μπορείτε να μπορείτε να επιστρέψετε οποιοδήποτε από αυτά.

Σημειώστε ότι ο αριθμός των περιοχών δεν έχει σημασία. Ειδικότερα, δεν απαιτείται η χρήση όσο το δυνατόν λιγότερων τοίχων.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο ακέραιους αριθμούς, χωρισμένους με κενό διάστημα, ~n~ και ~m (2 \le n \le 3\times 10^5,\,n - 1 \le m \le 3 \times 10^5)~ - ο αριθμός των περιοχών και των μονοπατιών, αντίστοιχα. Οι περιοχές αριθμούνται από ~1~ έως ~n~.

Η δεύτερη γραμμή εισόδου περιέχει ~n~ ακέραιους αριθμούς, χωρισμένους με κενό διάστημα, ~t_1, \cdots, t_n~, όπου ~t_i~ είναι ~-1~ εάν η ~i~-οστή περιοχή κατοικείται από αγελάδες, ~0~ εάν είναι αχρησιμοποίητη και ~1~ εάν είναι περιοχή πεζοπορίας.

Οι υπόλοιπες ~m~ γραμμές περιγράφουν μονοπάτια. Η ~j~-οστή από αυτές περιέχει τρεις, χωρισμένους με κενό διάστημα, ακέραιους αριθμούς ~a_j, b_j~ και ~l_j (1 \le a_j < _j \le n,\,0 \le l_j \le 10^9)~, που υποδηλώνουν ένα μονοπάτι μεταξύ των περιοχών ~a_j~ και ~b_j~, μήκους ~l_j~.

Είναι εγγυημένο ότι:

• μεταξύ δύο οποιωνδήποτε περιοχών υπάρχει το πολύ ένα μονοπάτι,
• είναι δυνατόν να περπατήσετε μεταξύ δύο περιοχών χρησιμοποιώντας μηδέν ή περισσότερα μονοπάτια,
• υπάρχει τουλάχιστον μία περιοχή που κατοικείται από αγελάδες,
• υπάρχει τουλάχιστον μία περιοχή πεζοπορίας

Έξοδος

Εάν είναι αδύνατο να κατασκευαστούν οι τοίχοι σύμφωνα με τις απαιτήσεις, η έξοδος είναι ~-1~.

Διαφορετικά, η πρώτη γραμμή της εξόδου θα πρέπει να περιέχει έναν ακέραιο αριθμό ~k~ - τον αριθμό των τοίχων που θέλετε να κατασκευάσετε. Η δεύτερη γραμμή θα πρέπει να περιέχει ~k~ ακέραιους αριθμούς - τους αριθμούς των περιοχών όπου θέλετε να χτίσετε τους τοίχους. (Οι αριθμοί αυτοί πρέπει να είναι διακριτοί αριθμοί μεταξύ ~1~ και ~n~, κλειστό διάστημα. Δεν χρειάζεται να είναι με κάποια συγκεκριμένη σειρά).

Η έξοδος θα γίνει αποδεκτή αν είναι ένα επιτρεπτό σύνολο τοίχων με ελάχιστη απόσταση.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~7~	~n \le 10~
~2~	~22~	Όλα τα μήκη είναι ~l_j = 0~
~3~	~16~	Υπάρχει ακριβώς μία περιοχή πεζοπορίας.
~4~	~11~	Υπάρχουν ακριβώς ~n - 1~ μονοπάτια (σε όρους θεωρίας γράφων, ο γράφος είναι ένα δέντρο).
~5~	~8~	Έχουμε ~n, m \le 2\,000~ και όλα τα μήκη είναι ~l_j = 1~.
~6~	~36~	Κανένας επιπλέον περιορισμός.

Παραδείγματα

input

10 14
1 0 1 0 0 0 0 0 -1 -1
1 2 1
1 6 1
2 3 1
2 5 2
3 4 1
4 5 1
4 8 2
5 6 1
5 7 1
6 7 2
6 10 1
7 8 1
7 9 1
8 9 1

output

3
4 5 6

Επεξήγηση του 1ου παραδείγματος:

Στο πρώτο παράδειγμα, η ελάχιστη δυνατή απόσταση είναι ~2~, η οποία επιτυγχάνεται με την τοποθέτηση τοίχων στις περιοχές ~4, 5~ και ~6~. Σημειώστε ότι δεν μπορεί κανείς να τοποθετήσει τοίχους στις περιοχές ~4, 2~ και ~6~, ακόμη και αν αυτό θα έδινε μια απόσταση ίση με ~1~, διότι τότε θα ήταν αδύνατο να ταξιδέψει κανείς μεταξύ των περιοχών πεζοπορίας ~1~ και ~3~ χωρίς να περάσει μέσα από τοίχο.

input

5 5
1 0 0 -1 0
1 2 1000
2 3 1000
3 4 10
4 5 10
1 5 10

output

2
3 5

Επεξήγηση του 2ου παραδείγματος:

Στο δεύτερο παράδειγμα, η απόσταση της περιοχής ~2~ είναι ~1000~ και η απόσταση της περιοχής ~3~ είναι ~30~, καθώς μπορεί να προσεγγιστεί μέσω της διαδρομής ~1-5-4-3~. (Υπενθυμίζεται ότι τα συνεργεία συντήρησης μπορούν να περάσουν μέσα από τοίχους και περιοχές που κατοικούνται από αγελάδες). Επομένως, θα πρέπει να τοποθετήσουμε τοίχους στις περιοχές ~5~ και ~3~ (όχι ~2~) και η απόσταση θα είναι ~30~.

input

4 3
1 0 -1 1
1 2 0
2 3 21
2 4 13

output

-1

Σημείωση: Σε όλα τα σχήματα, το μπλε (διακεκομμένο) χρησιμοποιείται για τις περιοχές πεζοπορίας, το καφέ (γεμάτο) για τις περιοχές που κατοικούνται από αγελάδες και το πορτοκαλί (διακεκομμένο) για τους τοίχους.