After the treacherous and exhausting escape from the most northern factory and mine in the world, The elves find themselves free of all duty and are stuck on the large island known as Antarctica. After emerging from the factory, the elves had decided to commit grand theft auto and use Santa's sleigh as a getaway vehicle. Upon departure, the elves discovered their incredibly terrible ability to pilot Santa's sleigh due to their knowledge limited to mining coal and building toys. The 3 smartest elves in the group (they also crashed the sleigh and somehow ended up in Antarctica) are now tasked with figuring out how all the stranded elves can get to civilization so they can enjoy luxuries such as heating, proper food, proper beds, proper air, proper toilets, and proper rights.

The 3 elves meet and discuss what to do in their conundrum. Elf 1, Stanley begins the meeting by stating, "I have no idea where we are and which direction we came from." Elf 2, George aggressively responds to him by saying "THIS IS ALL YOUR FAULT STANLEY! IF ONLY YOU HADN'T TURNED LEFT WHEN I SAID TO TURN RIGHT WE WOULD HAVE FOUND CIVILIZATION!" The third elf, Michael Breckenridge cleverly expresses, "Uh oh we in big trouble guys. I don't think it is the warm beach."

Stanley: "Oops, looks like I might have read the backside of the map."
George: "Ok so we're in the middle of nowhere surrounded by snow in every direction with a broken sleigh and some presents."
Stanley: "It does appear that way, George. Which direction do you guys think we should go to get to the beach?"
Michael Breckenridge: "I think it feels warmer in that direction (points to some snow in the distance)."
George: "I can't believe that the third smartest elf is you, Michael Breckenridge."
Stanley: "Hey! Don't be rude George, we're a team and need to work together to get out of this mess. Since the presents are the only source of food, how do you guys think we bring them in that direction? (points towards the snow)"
George: "You do realize that we have 2.9 million elves with us right? They can help bring our supplies (presents)."
Stanley: "Astute observation! Let's get moving in that direction (points towards the snow)."

George: "We're at that clump of snow you guys wanted to move to. It looks the same as before just without a sleigh"
Stanley: "Uh oh! It looks like we made a mistake in calculations!"
George: "... I think I'm going to give up"
Michael Breckenridge: "Sounds like a plan, man!"
Stanley: "Come on guys, the other 2.9 million elves are relying on us to reach the warm beach! I think we should try a different direction. How about over there? (points to some snow)"
George: "Fine."

Stanley: "After all those direction changes, I think we should stop switching directions and just keep on going in one."
George: "HOW ARE WE BACK AT THE SLEIGH. WHY DID I TRUST YOU WITH THE DIRECTIONS AGAIN."
Michael Breckenridge: "I think this place is familiar."
Stanley: "ok let us all calm down and walk in that direction. (points to some snow)"
George: "NO! WE'RE GOING IN THAT DIRECTION! (points to some other snow)"

(3 days later)

George: "Ok I'm actually giving up. I'm gonna sit right here for the rest of my life."
Stanley: "I agree, who cares about the 2.9 million other elves."
Michael Breckenridge: "I'm going to build a wall out of our presents to pass the time"
George: "I think I'll join you, I'm so bored"
Stanley: "Me too, I'll also get the other 2.9 million elves to join us"

(they are unable to get rid of their building habits)

George: "Wait why do I only see like 4 or 5 or 6 presents?"
Michael Breckenridge: "I think I forgot to bring the present we were going to steal from Santa onto the sleigh."
George: "Bruh."
Stanley: "I have a good idea! Let us go back to the most northern factory to steal them!"
Michael Breckenridge: "Ok, sounds like a plan, man!"
George: "How do we even get to the North Pole without the sleigh???"
Stanley: "Every part of the sleigh can fly, you know, we just sit on the broken parts and fly"
George: "Bruh why didn't you say that at the beginning!"
Stanley: "I forgot."
Michael Breckenridge: "Ok! Let's reverse the direction, all 2.9 million elves!"

(3 days later)

George: "FINALLY! I see the sleigh! it's a miracle that we didn't get lost!"
Michael Breckenridge: "Let's goooo! We're finally getting out of here!"
Stanley: "Let's goooo!"
George: "Lets goooo!"

The 2.9 million + 3 elves proceed to salvage as many parts as possible from the sleigh before happily boarding their individual wood planks and pieces of metal and taking off into the horizon. Due to the restless nature of the elves, considering the experience they had just gone through, they are asking you to help them. They plan to fly over many different tourist destinations all over the world and want to know the shortest path to the North Pole while flying over these destinations. The elves start at destination ~1~ and are trying to get to the North Pole at destination ~N~. Due to increased airspace security (for some odd reason), they must take specific bidirectional paths between these destinations of a certain distance to avoid prison. As well as the shortest path, they also want to know how many shortest paths with unique sequences of unique tourist destinations exist.

Input Specifications

The first line contains ~N~, ~(1 \le N \le 10^4)~, the total number of tourist destinations, and ~M~, ~(1 \le M \le 10^5)~, the number of paths between destinations.
The following M lines contain integers ~a~, ~(1 \le a \le N)~, ~b~ ~(1 \le b \le N)~, and ~d~, ~(1 \le d \le 10^4)~, representing a bidirecional path between ~a~ and ~b~ of distance ~d~.

Output Specifications

Output the distance of the shortest path to the North Pole followed by the number of shortest paths that exist on the next line. If no paths exist between the start and the North Pole, output -1

Sample Input 1

3 3
1 2 1
2 3 1
1 3 3

Sample Output 1

2
1

Explanation of Sample Output 1

The only shortest path is 1 2 3 of distance 2

Sample Input 2

7 9
1 2 1
1 3 2
2 4 2
3 5 3
5 4 3
4 6 1
6 7 2
2 7 5
5 7 1

Sample Output 2

6
3

Explanation of Sample Output 2

The shortest paths are 1 2 7, 1 2 4 6 7, and 1 3 5 7