PROGRAMMING:The Whimper of Universe
What does our future hold? How will the universe meet its end? Over the whole human history, controversy on whether the universe ends in fire or ice has never come to an end. But now, with the second law of thermodynamics, maybe we can conclude that the universe ends in not a giant explosion, but a whimper.
After 10^377 years, this universe is approaching its end. Everything goes together, becoming a black hole, and nothing is left except some dying black dwarf stars which are the only places for possibly remaining civilizations to feed on. Now you are the God and only Sylvie is lingering on with her last breath of life in this universe created by you. With mercy, you are affected by her strong will to survive, so you decide, if she solves the problem you present her, you will ship her to the next universe you create where there are still colours.
So you whispered by her ear: '**Every black dwarf star has energy, and a string of letters with it**. If you **live long enough to collect the largest amount of energy from those black dwarf stars, keeping on collecting strings of letters of each star you pass, combining them in turn** along the journey, you will find the encoded answer therein. **Decode it by finding the sequence of letters with the most front alphabetic order among permutations of the original without changing circular order of its letters**. For example, if you pass three stars with string "b", "cd" and "a" respectively, and combines them to get "bcda", you can then decode it and get the answer "abcd".'
**Sylvie dies as soon as her energy runs out, and when arriving at a star, the road carrying her there takes certain amount of her energy and disappears, but she collects all the energy of that star which is, sadly, strictly nonrenewable.**
There are* N* black dwarf stars and *M* directed roads between them in the universe and Sylvie is now on star *S1* with roads leading to other stars and the energy costs along these roads are given. **Every time Sylvie arrives at a planet, the string of the planet is collected again**.
Because of the incredible deficiency of energy in the dying universe, even one spark of thought will take billions of years within which Sylvie will die for sure together with the universe. So Sylvie has to get the right answer quickly.
Since you are curious and almighty, you think of the answer immediately after having invented the problem. And in the meanwhile, the idea that putting your wisdom down in form of an ancient language invented by human beings for their computers has come to your mind for fun. Try doing it now!
### Input Specification:
The first line are two integers *N* and *M* (N>0,M>0,N<=20 M<=300) and the second line, *N* integers, of which the ith integer describes the energy of the ith black dwarf star.
*M* lines with three integers *x,y,e* are following, meaning star *Sx* has one directed road leading to star *Sy* costing *e* energy on the road.
Finally there are *N* lines, of which each is a string of letters – the string can be found on the *ith* star (at the beginning, Sylvie has the energy of the first black dwarf star).
### Output Specification:
Altogether two lines, of which the first line is the string of letters you have decoded, while the second, the amount of energy Sylvie collected. There is only one path to collect the largest amount of energy.
### Sample Input:
Write a sample input here. For example:
```in
4 5
10 10 10 20
1 2 3
1 3 5
2 4 10
3 4 5
1 4 1
b
f
cd
a
```
### Sample Output:
Write the corresponding sample output here. For example:
```out
abcd
thirty
```
answer：If there is no answer, please comment
**Given a weighted digraph, each node has a certain amount of energy. Starting from node 1, each path can only be taken once to find the path that can collect the maximum energy. Then, according to this path, the string on the passing node is connected into a long string, and the circular isomorphic string of the string is found.
**Idea * *: it's very easy to find the path to collect the maximum energy, because the data is up to 20 nodes and 300 directed edges, so you can directly record the path by DFS. After finding the path, connect the strings on the nodes in turn and store them in the character array.
Next is the main play: how to find a cyclic isomorphic string with the smallest dictionary order.
**String algorithm: minimum representation**
Minimum representation is a special algorithm for finding cyclic isomorphic strings with minimum lexicographic order. Its time complexity is a linear function of string length
Suppose that a string of length n exists in s, in order to find the cyclic isomorphic string with the minimum lexicographic order, we only need to find its starting position. Linear scan s [] as the beginning of each position, and then update the answer.
Now let I and j start from 0 and 1, I = 0, j = 1. Because I want to compare the cyclic isomorphic strings starting from I and j, I and j are different at any time. Next, let a variable K denote the length that has been compared. Then we will compare s [i + k] and s [J + k]. For s [i + k] and s [J + k], there are three cases:
1、s[i+k]>s[j+k]
If s [i + k] > s [J + k], and every bit before k that starts with I and j is the same, then it is obvious that all cyclic isomorphic strings starting from s [i] to s [i + k] cannot be minimum lexicographic, so I + = K + 1.
2、s[i+k]==s[j+k]
If the two are the same, then K + + enters the next loop. If K is n, then every bit of the string is the same. Output any bit and exit the loop.
3、s[i+k]The same as 1, j + = K + 1.
Note that if the array is treated as a ring, then in fact I + K and j + K need to be% n. when I and j are equal, just take any self addition. Finally, when I and j are treated as N or K = = n, exit the loop and output the one with smaller I and J.
After 10^377 years, this universe is approaching its end. Everything goes together, becoming a black hole, and nothing is left except some dying black dwarf stars which are the only places for possibly remaining civilizations to feed on. Now you are the God and only Sylvie is lingering on with her last breath of life in this universe created by you. With mercy, you are affected by her strong will to survive, so you decide, if she solves the problem you present her, you will ship her to the next universe you create where there are still colours.
So you whispered by her ear: '**Every black dwarf star has energy, and a string of letters with it**. If you **live long enough to collect the largest amount of energy from those black dwarf stars, keeping on collecting strings of letters of each star you pass, combining them in turn** along the journey, you will find the encoded answer therein. **Decode it by finding the sequence of letters with the most front alphabetic order among permutations of the original without changing circular order of its letters**. For example, if you pass three stars with string "b", "cd" and "a" respectively, and combines them to get "bcda", you can then decode it and get the answer "abcd".'
**Sylvie dies as soon as her energy runs out, and when arriving at a star, the road carrying her there takes certain amount of her energy and disappears, but she collects all the energy of that star which is, sadly, strictly nonrenewable.**
There are* N* black dwarf stars and *M* directed roads between them in the universe and Sylvie is now on star *S1* with roads leading to other stars and the energy costs along these roads are given. **Every time Sylvie arrives at a planet, the string of the planet is collected again**.
Because of the incredible deficiency of energy in the dying universe, even one spark of thought will take billions of years within which Sylvie will die for sure together with the universe. So Sylvie has to get the right answer quickly.
Since you are curious and almighty, you think of the answer immediately after having invented the problem. And in the meanwhile, the idea that putting your wisdom down in form of an ancient language invented by human beings for their computers has come to your mind for fun. Try doing it now!
### Input Specification:
The first line are two integers *N* and *M* (N>0,M>0,N<=20 M<=300) and the second line, *N* integers, of which the ith integer describes the energy of the ith black dwarf star.
*M* lines with three integers *x,y,e* are following, meaning star *Sx* has one directed road leading to star *Sy* costing *e* energy on the road.
Finally there are *N* lines, of which each is a string of letters – the string can be found on the *ith* star (at the beginning, Sylvie has the energy of the first black dwarf star).
### Output Specification:
Altogether two lines, of which the first line is the string of letters you have decoded, while the second, the amount of energy Sylvie collected. There is only one path to collect the largest amount of energy.
### Sample Input:
Write a sample input here. For example:
```in
4 5
10 10 10 20
1 2 3
1 3 5
2 4 10
3 4 5
1 4 1
b
f
cd
a
```
### Sample Output:
Write the corresponding sample output here. For example:
```out
abcd
thirty
```
answer：If there is no answer, please comment
**Given a weighted digraph, each node has a certain amount of energy. Starting from node 1, each path can only be taken once to find the path that can collect the maximum energy. Then, according to this path, the string on the passing node is connected into a long string, and the circular isomorphic string of the string is found.
**Idea * *: it's very easy to find the path to collect the maximum energy, because the data is up to 20 nodes and 300 directed edges, so you can directly record the path by DFS. After finding the path, connect the strings on the nodes in turn and store them in the character array.
Next is the main play: how to find a cyclic isomorphic string with the smallest dictionary order.
**String algorithm: minimum representation**
Minimum representation is a special algorithm for finding cyclic isomorphic strings with minimum lexicographic order. Its time complexity is a linear function of string length
Suppose that a string of length n exists in s, in order to find the cyclic isomorphic string with the minimum lexicographic order, we only need to find its starting position. Linear scan s [] as the beginning of each position, and then update the answer.
Now let I and j start from 0 and 1, I = 0, j = 1. Because I want to compare the cyclic isomorphic strings starting from I and j, I and j are different at any time. Next, let a variable K denote the length that has been compared. Then we will compare s [i + k] and s [J + k]. For s [i + k] and s [J + k], there are three cases:
1、s[i+k]>s[j+k]
If s [i + k] > s [J + k], and every bit before k that starts with I and j is the same, then it is obvious that all cyclic isomorphic strings starting from s [i] to s [i + k] cannot be minimum lexicographic, so I + = K + 1.
2、s[i+k]==s[j+k]
If the two are the same, then K + + enters the next loop. If K is n, then every bit of the string is the same. Output any bit and exit the loop.
3、s[i+k]
Note that if the array is treated as a ring, then in fact I + K and j + K need to be% n. when I and j are equal, just take any self addition. Finally, when I and j are treated as N or K = = n, exit the loop and output the one with smaller I and J.