#include 
#include 
#include 
using namespace std;

struct node
{
    int idx;
    long long cost;
    int pop;
    node(){}
    node(int _idx, long long _cost, int _pop)
    {
        idx=_idx;
        cost=_cost;
        pop=_pop;
    }
    bool operator <(const node &tmp)const
    {
        return cost>tmp.cost;
    }
};
vector>par[100005];
long long dis[100005][2];

int main()
{
    ios_base::sync_with_stdio(false);
    long long a,b,x,y,z;
    cin>>a>>b;
    int i, j;
    
    for( i=0;i>x>>y>>z;
        par[x].push_back({y,z});
    }
    priority_queueQ;
    Q.push(node(1,0,0));
    for( i=0;i<=a;i++)
    {
        for( j=0;j<2;j++)
        {
            dis[i][j]=1e18;
        }
    }
    long long sosed, r;
    dis[1][0]=0;
    dis[1][1] = 0;
    while(!Q.empty())
    {
        node teme=Q.top();
        Q.pop();
        
        if(teme.cost > dis[teme.idx][teme.pop]) continue;
        for( i=0;i