Την Κυριακή του Πάσχα, στο χωριό του Παντελή, έχει στηθεί τρικούβερτο γλέντι. Τα τραπέζια έχουν τοποθετηθεί σε ένα μεγάλο υπαίθριο χωράφι, οι οβελίες ψήνονται από το πρωί και η ορχήστρα παίζει ασταμάτητα. Ο Παντελής είναι υπεύθυνος για τη διαδικασία σερβιρίσματος του φαγητού και έχει αναθέσει σε φίλους του το ρόλο των γκαρσονιών. Για να διευκολύνει τη διαδικασία, ο Παντελής έχει δώσει οδηγίες στα γκαρσόνια:
1) Αρχικά ένα γκαρσόνι θα κατευθύνεται σε ένα τραπέζι και θα δέχεται την παραγγελία. Μπορείτε να υποθέσετε ότι ο Παντελής έχει στη διάθεσή του τόσα γκαρσόνια όσα και τα τραπέζια.
2) Μετά το γκαρσόνι θα κατευθύνεται στο χώρο ψησίματος, όπου θα δίνει την παραγγελία και θα πιάνει να φαγητά που έχει παραγγείλει το τραπέζι.
3) Το γκαρσόνι θα μεταφέρει τα φαγητά στο τραπέζι που τα έχει παραγγείλει.
4) Μόλις σερβίρει τα φαγητά, το γκαρσόνι θα εισπράττει ένα συμβολικό ποσό από το τραπέζι και θα το παίρνει στο ταμείο που θα έχει στηθεί για τις εισπράξεις.
Στον υπαίθριο χώρο υπάρχουν συνολικά N χώροι αναφοράς. Ανάμεσα σε αυτούς υπάρχουν:
• Ένας χώρος S, στον οποίο βρίσκονται αρχικά όλα τα γκαρσόνια για να τους δοθούν οδηγίες από τον Παντελή.
• Ένας χώρος R, ο χώρος ψησίματος, όπου βρίσκονται όλα τα φαγητά.
• Ένας χώρος C, το ταμείο που έχει στηθεί για τις εισπράξεις.
• Κάποια, ή και όλα, από σημεία S, R και C μπορεί να είναι τα ίδια.
• Οι υπόλοιποι χώροι αναφοράς, εκτός από τους τρεις πιο πάνω, να θεωρηθούν ότι είναι τραπέζια και θα πρέπει να εξυπηρετηθούν.
• Υπάρχουν Μ συνολικά διαδρομές διπλής κατεύθυνσης που ενώνουν τους πιο πάνω χώρους, όπου κάθε διαδρομή έχει συγκεκριμένο χρονικό κόστος. Κάποιοι χώροι μπορεί να συνδέονται με περισσότερες από μια διαδρομές, αναλόγως με το χρόνο πρόσβασης.
Ο Παντελής θέλει να γνωρίζει ποιος θα είναι ο ελάχιστος χρόνος για να σερβίρουν όλα τα τραπέζια και να εισπραχθούν όλα τα ποσά. Δηλαδή θέλει να γνωρίζει πόση ώρα θα χρειαστούν όλα τα γκαρσόνια, ξεκινώντας από το χώρο αφετηρίας S, να πάρουν παραγγελίες από τα τραπέζια, να πάνε στο χώρο ψησίματος R, να επιστρέψουν στα τραπέζια και να αφήσουν τα φαγητά, να εισπράξουν το συμβολικό ποσό και να συγκεντρωθούν στο ταμείο C. Να σημειωθεί ότι μόνο οι μετακινήσεις στοιχίζουν χρονικά στα γκαρσόνια.
Δεδομένα εισόδου
• Στην πρώτη γραμμή θα εμφανίζεται ένας ακέραιος αριθμός Τ, το πλήθος των αρχείων ελέγχου (testcases).
• Για κάθε ένα από τα αρχεία ελέγχου, θα εμφανίζονται δύο ακέραιοι Ν, το πλήθος των χώρων αναφοράς στο γλέντι και Μ, οι διαδρομές διπλής κατεύθυνσης που συνδέουν αυτούς τους χώρους μεταξύ τους.
• Κάθε μια από τις επόμενες Μ γραμμές θα περιέχει τρεις ακέραιους a, b και w, που σημαίνει ότι υπάρχει διαδρομή που ενώνει το χώρο a με το χώρο b (και αντίθετα), με χρονικό κόστος w. Μπορεί να υπάρχουν και περισσότερες από μια διαδρομές που να συνδέουν δύο χώρους.
• Η επόμενη γραμμή θα περιέχει τρεις ακέραιους αριθμούς, το S, το R και το C. Το σημείο εκκίνησης των γκαρσονιών, το χώρο ψησίματος και το ταμείο. Οι ακέραιοι αυτοί δεν είναι απαραίτητα διαφορετικοί μεταξύ τους.
Δεδομένα εξόδου
Σε κάθε γραμμή να εμφανίζεται ένας ακέραιος, ο ελάχιστος χρόνος για να εξυπηρετηθούν όλα τα τραπέζια.
Περιορισμοί
• 1 <= T <= 10
• 4 <=N <= 100
• 1 <= M <= 10000
• 1 <= a, b, S, R, C <= N
• 1 <= w <= 100
Ο γράφος του παραδείγματος είναι ο πιο κάτω:
Η αφετηρία βρίσκεται στη θέση 1, τα δύο τραπέζια βρίσκονται στις θέσεις 2 και 3, ο χώρος ψησίματος βρίσκεται στη θέση 4 και το ταμείο στη θέση 5.
Το πρώτο γκαρσόνι που θα εξυπηρετήσει το τραπέζι 2, ξεκινά από τη θέση 1 και κάνει τη διαδρομή 1->2 για να πιάσει την παραγγελία (κόστος 2), τη διαδρομή 2->4->2 για να πάει στο χώρο ψησίματος και να επιστρέψει με τα φαγητά (κόστος 4) και τη διαδρομή 2->4->5 για να πάρει τα χρήματα στο ταμείο (κόστος 3), άρα συνολικό χρονικό κόστος 2+4+3 = 9.
Το δεύτερο γκαρσόνι που θα εξυπηρετήσει το τραπέζι 3, ξεκινά από τη θέση 1 και κάνει τη διαδρομή 1->2->3 για να πιάσει την παραγγελία (κόστος 5), τη διαδρομή 3->2->4->2->3 για να πάει στο χώρο ψησίματος και να επιστρέψει με τα φαγητά (κόστος 10) και τη διαδρομή 3->2->4->5 για να πάρει τα χρήματα στο ταμείο (κόστος 6), άρα συνολικό χρονικό κόστος 5+10+6 = 21.
Άρα ο ελάχιστος χρόνος εξυπηρέτησης για όλα τα τραπέζια θα είναι 21, ο χρόνος που θα χρειαστεί το δεύτερο γκαρσόνι για να εξυπηρετήσει το τραπέζι 3.