测试数据来自 system/1411

背景

9.19是青子的生日...
而在那日晚,基德发出了盗窃"忧郁的生日"的预告函.
快斗在两难的抉择下,最终决定:以最快速度将"忧郁的生日"收入囊中,再赶去为青子表演魔术--这是他对青子的允诺.

描述

"忧郁的生日"被保存在一个深不可测的大楼里.而从大门到最里面的房间有无数条路径.整个大楼可以被看做一个巨大的无向图,有些
房间之间有路,而有些没有.每条路要消耗基德不一样的时间.在最里面的房间内存放着"忧郁的生日".这块宝石被一层密码锁保护着.
打开这层密码锁也需要一段时间.假设基德盗窃时没有人来干扰(警卫都干什么吃的).给出基德开始盗窃的时间,整个大楼中连通的情
况以及打开这个密码锁的时间.求出快斗能对青子允诺到达生日会场的最早时间.若此时间晚于24:00则输出"Sad".

格式

输入格式

输入文件共k+3行.
第一行,是基德开始盗窃的时间.格式为形如"xx:xx"的24小时制形式(如13:00);
第二行到第k+2行为大楼的连通情况.
第二行共2个整数n,k.n为房间总数,共k对房间之间有路径.进口为1号房间,"忧郁的生日"存放在n号房间里.
第三行到第k+2行,每行共3个整数a,b,c.表示a号和b号房间之间有路径,该路径费时为c分钟.
第k+3行为打开密码锁的时间,格式为"x min/second/hour"表示打开密码锁需要x分钟/秒/小时.

输出格式

输出共一行,输出快斗能允诺青子的最早时间,格式如同输入中的开始盗窃时间格式"xx:xx",24小时制.若最早时间超过24:00则输出
"Sad".

样例1

样例输入1

17:00
3 3
1 2 1
2 3 1
1 3 4
3min

样例输出1

17:05

提示

数据保证一定能抵达中心房间。需要注意的是，输入数据中可能会出现0号结点。这些数据均需被忽略不计。而输入中开始时间必定
遵守"xx:xx"格式，如"05:00";但输出中你必须这样表示:"5:00"而不应出现一开始的“0”。

来源

From 玛维-影之歌
永远守望vijos...