Remember the defeated demons? the survivals go back and told the big boss, big boss was so angry that he decide to fight TT back. The big boss used his strong power and made many roads, TT and her army was in point 1, big boss was in point N. TT wanted to go as quickly as possible to defeat the boss, let's find out the proper way to go.

For each case, there was two integers N and M, big boss was in N(1 <= N <= 100), and there are M(1 <= M <= 2000) roads. then M lines followed. The ith line contains X,Y,dis,means that road X to road Y's distance is dis. there is no any other roads if not given.

For each case, output the shortest distance from 1 to N.