from collections import defaultdict,deque
from sys import stdin
from heapq import heappush,heappop

g = defaultdict(list)
n,m = map(int,input().split())
dist = [float('inf')] * (n+1)
st = [False for _ in range(n+1)]
def djikstra():
    q = [[0,1]]
    dist[1] = 0
    while q:
        _,w = heappop(q)
        if st[w]:
            continue
        st[w] = True
        for u,d in g[w]:
            if dist[u] > dist[w] + d:
                dist[u] = dist[w] + d;
                heappush(q,[dist[u],u])
    return dist[n] if dist[n] != float('inf') else -1




for _ in range(m):
    a,b,c = map(int,stdin.readline().split())
    g[a].append((b,c))

print(djikstra())

from sys import stdin
from collections import defaultdict
n,m = map(int,input().split())
g = defaultdict(list)
dist = [float('inf')] * (n+1)
st = [False] * (n+1)
def djikstra(n):
    dist[1] = 0
    for i in range(n-1):
        t = -1
        for j in range(n):
            if not st[j] and (t == -1 or dist[t]>dist[j]):
                t = j
        st[t] = True
        for w,d in g[t]:
            dist[w] = min(dist[w],dist[t] + d)

    return dist[n] if dist[n] != float('inf') else -1 


for _ in range(m):
    a,b,c = map(int,input().split())
    g[a].append((b,c))


print(djikstra(n))

from collections import defaultdict,deque

n,m = map(int,input().split())
g = defaultdict(list)
d = [0] * (n+1)
def topsort(n):
    q = deque()
    for i in range(1,n+1):
        if not d[i]:
            q.append(i)
    ans = []
    while q:
        w = q.popleft()
        ans.append(w)
        for u in g[w]:
            d[u] -= 1
            if not d[u]:
                q.append(u)
    if len(ans) == n:
        print(" ".join(map(str,ans)))
    else:
        print(-1)


for _ in range(m):
    a,b = map(int,input().split())
    d[b] += 1
    g[a].append(b)
topsort(n)

n,m = map(int,input().split())
h = [-1] * (n+1);ne = [0] * (m+1);e = [0]*(m+1)
idx = 0
q = [0] * (n+1);d =[-1]*(n+1)
def add(a,b):
    global idx
    e[idx] = b;ne[idx] = h[a];h[a] = idx
    idx += 1

def bfs():
    hh = 0;tt =0 
    q[0] = 1
    d[1] = 0
    while hh <= tt:
        w = q[hh];hh+=1
        i = h[w]
        while i != -1:
            j = e[i]
            if d[j] == -1:
                d[j] = d[w] + 1
                q[tt+1] = j;tt += 1
            i = ne[i]
    return d[n]
for _ in range(m):
    a,b = map(int,input().split())
    add(a,b)
print(bfs())

n = int(input())
h = [-1] * (2*n+10);ne = [0] * (2*n+10);e = [0]*(2*n+10)
idx = 0;ans = n
st = [False]*(n+1)
def add(a,b):
    global idx
    e[idx] = b;ne[idx] = h[a];h[a] = idx;
    idx += 1

def dfs(u):
    global n,ans
    res = 0;Sum = 0;
    i = h[u];st[u] = True

    while i!=-1:
        j = e[i];
        i = ne[i]
        if st[j]:
            continue
        s = dfs(j);Sum += s;
        res = max(res,s)



    res = max(res,n-Sum - 1)
    ans = min(ans,res)
    return Sum + 1



for _ in range(n-1):
    a,b = map(int,input().split())
    add(a,b);add(b,a)
dfs(1)
print(ans)

from collections import deque
n,m = map(int,input().split())
g = [input().split() for _ in range(n)]

def bfs(g):
    global n,m
    st = [[False for _ in range(m)] for i in range(n)]
    q = deque([(0,0)])
    step  = 0
    st[0][0] = True
    while q:
        size = len(q)
        for _ in range(size):
            i,j = q.popleft()
            if i == n - 1 and j == m - 1:
                return step

            for dx,dy in [[1,0],[-1,0],[0,-1],[0,1]]:
                x,y = dx + i,dy + j
                if x == n or y == m or x<0 or y<0 or st[x][y] or g[x][y] == '1':
                    continue
                st[x][y] = True

                q.append([x,y])
        step += 1
    return -1
print(bfs(g))

n = int(input())

g = [['.' for i in range(n)] for j in range(n)]
col = [False]*n;left = [False]*(2*n-1)
right = [False]*(2*n-1)


def dfs(i):
    global n
    if i == n:
        for j in g:
            print(''.join(j))
        print()
        return

    for j in range(n):
        if col[j] or left[i+j] or right[j-i+n-1]:
            continue
        col[j],left[i+j],right[j-i+n-1] = True,True,True
        g[i][j] = 'Q'
        dfs(i+1)
        col[j],left[i+j],right[j-i+n-1] = False,False,False
        g[i][j] = '.'


dfs(0)

from copy import deepcopy
n = int(input())
ans = []

def dfs(i,n,mark,t):
    if i > n:
        print(" ".join(map(str,t)))

        return
    for j in range(1,n+1):
        if mark>>j&1:
            continue
        t.append(j)
        dfs(i+1,n,mark|(1<<j),t)
        t.pop()

dfs(1,n,0,[])

#include <iostream>

using namespace std;

const int N = 50010;

int n, m;
int p[N], d[N];

int find(int x)
{
    if (p[x] != x)
    {
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;

    int res = 0;
    while (m -- )
    {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);

        if (x > n || y > n) res ++ ;
        else
        {
            int px = find(x), py = find(y);
            if (t == 1)
            {
                if (px == py && (d[x] - d[y]) % 3) res ++ ;
                else if (px != py)
                {
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            }
            else
            {
                if (px == py && (d[x] - d[y] - 1) % 3) res ++ ;
                else if (px != py)
                {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }

    printf("%d\n", res);

    return 0;
}

n,m = map(int,input().split())
s = input().strip()
hash = [0] * (n+ 1)
p = [1] * (n+1)
MOD = 1<<64
for i in range(n):
    hash[i+1] = (hash[i] * 131 + ord(s[i]))%MOD
    p[i+1] = (p[i] * 131) % MOD

def hash_value(l,r):
    return (hash[r] - hash[l-1]*p[r-l+1])%MOD

for _ in range(m):
    l1,r1,l2,r2 = map(int,input().split())

    print("Yes" if hash_value(l1,r1) == hash_value(l2,r2) else "No")