头像

The__Flash




离线:3小时前


活动打卡代码 AcWing 2234. 多源汇最大流

The__Flash
5个月前
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int M = (int)1e4;
const int N = (int)2e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
const double eps = 1e-9;

struct Graph
{
    int n, m, S, T, cnt;
    int head[M + 5];

    struct node
    {
        int v, w, nx;
    }Edge[N * 2 + 5];

    int d[M + 5];
    int cur[M + 5];
    int q[M + 5], l, r;

    void init()
    {
        cnt = 0;
        for(int i = 0; i <= n; ++i)
        {
            head[i] = -1;
        }
    }

    void add(int u, int v, int w)
    {
        Edge[cnt].v = v;
        Edge[cnt].w = w;
        Edge[cnt].nx = head[u];
        head[u] = cnt++;
    }

    bool bfs()
    {
        l = 1, r = 0;
        for(int i = 1; i <= n; ++i) d[i] = -1;
        q[++r] = S, d[S] = 0, cur[S] = head[S];
        while(l <= r)
        {
            int u = q[l++];
            if(u == T) return 1;
            for(int i = head[u]; ~i; i = Edge[i].nx)
            {
                int v = Edge[i].v;
                if(d[v] == -1 && Edge[i].w)
                {
                    d[v] = d[u] + 1;
                    cur[v] = head[v];
                    q[++r] = v;
                }
            }
        }
        return 0;
    }

    int dfs(int u, int limit)
    {
        if(u == T) return limit;
        int flow = 0;
        for(int i = cur[u]; ~i && flow < limit; i = Edge[i].nx)
        {
            cur[u] = i;
            int v = Edge[i].v;
            if(d[v] == d[u] + 1 && Edge[i].w)
            {
                int t = dfs(v, min(Edge[i].w, limit - flow));
                if(!t) d[v] = -1;
                Edge[i].w -= t, Edge[i^1].w += t, flow += t;
            }
        }
        return flow;
    }

    int Dinic()
    {
        int r = 0, flow;
        while(bfs()) while(flow = dfs(S, inf)) r += flow;
        return r;
    }
}G;

int n, m, Sc, Tc;

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    scanf("%d %d %d %d", &n, &m, &Sc, &Tc); G.n = n + 1; G.init(); G.S = 0, G.T = n + 1;
    for(int i = 1, S; i <= Sc; ++i) scanf("%d", &S), G.add(0, S, inf), G.add(S, 0, 0);
    for(int i = 1, T; i <= Tc; ++i) scanf("%d", &T), G.add(T, n + 1, inf), G.add(n + 1, T, 0);
    for(int i = 1, u, v, w; i <= m; ++i) scanf("%d %d %d", &u, &v, &w), G.add(u, v, w), G.add(v, u, 0);
    printf("%d\n", G.Dinic());
    return 0;
}



The__Flash
5个月前
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int M = (int)6e4;
const int N = (int)1e6;
const int inf = 2147483647;
const ll mod = (ll)998244353;
const double eps = 1e-9;

struct Graph
{
    int n, m, S, T, cnt;
    int head[M + 5];

    struct node
    {
        int v, w, nx;
    }Edge[N * 2 + 5];

    int d[M + 5];
    int cur[M + 5];
    int q[M + 5], l, r;

    void init()
    {
        cnt = 0;
        for(int i = 0; i <= n; ++i)
        {
            head[i] = -1;
        }
    }

    void add(int u, int v, int w)
    {
        Edge[cnt].v = v;
        Edge[cnt].w = w;
        Edge[cnt].nx = head[u];
        head[u] = cnt++;
    }

    bool bfs()
    {
        l = 1, r = 0;
        for(int i = 1; i <= n; ++i) d[i] = -1;
        q[++r] = S, d[S] = 0, cur[S] = head[S];
        while(l <= r)
        {
            int u = q[l++];
            if(u == T) return 1;
            for(int i = head[u]; ~i; i = Edge[i].nx)
            {
                int v = Edge[i].v;
                if(d[v] == -1 && Edge[i].w)
                {
                    d[v] = d[u] + 1;
                    cur[v] = head[v];
                    q[++r] = v;
                }
            }
        }
        return 0;
    }

    int dfs(int u, int limit)
    {
        if(u == T) return limit;
        int flow = 0;
        for(int i = cur[u]; ~i && flow < limit; i = Edge[i].nx)
        {
            cur[u] = i;
            int v = Edge[i].v;
            if(d[v] == d[u] + 1 && Edge[i].w)
            {
                int t = dfs(v, min(Edge[i].w, limit - flow));
                if(!t) d[v] = -1;
                Edge[i].w -= t, Edge[i^1].w += t, flow += t;
            }
        }
        return flow;
    }

    int Dinic()
    {
        int r = 0, flow;
        while(bfs()) while(flow = dfs(S, inf)) r += flow;
        return r;
    }
}G;

int n, m, S, T;
int a[N + 5], b[N + 5], c[N + 5], d[N + 5];
int s[M + 5];

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    scanf("%d %d %d %d", &n, &m, &S, &T); G.n = n + 1; G.init(); G.S = 0, G.T = n + 1;
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
        s[b[i]] += c[i], s[a[i]] -= c[i];
        G.add(a[i], b[i], d[i] - c[i]), G.add(b[i], a[i], 0);
    }
    int tot = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(s[i] > 0)        G.add(0, i, s[i]), G.add(i, 0, 0), tot += s[i];
        else if(s[i] < 0)   G.add(i, n + 1, -s[i]), G.add(n + 1, i, 0);
    }
    G.add(T, S, inf), G.add(S, T, 0);
    if(G.Dinic() < tot) {printf("No Solution\n"); return 0;}
    int ans = G.Edge[G.cnt - 1].w;
    G.Edge[G.cnt - 1].w = G.Edge[G.cnt - 2].w = 0;
    G.S = T, G.T = S;
    ans -= G.Dinic();
    printf("%d\n", ans);
    return 0;
}



The__Flash
5个月前
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int M = (int)2e2;
const int N = (int)20800;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;
const double eps = 1e-9;

struct Graph
{
    int n, m, S, T, cnt;
    int head[M + 5];

    struct node
    {
        int v, w, nx;
    }Edge[N * 2 + 5];

    int d[M + 5];
    int cur[M + 5];
    int q[M + 5], l, r;

    void init()
    {
        cnt = 0;
        for(int i = 0; i <= n; ++i)
        {
            head[i] = -1;
        }
    }

    void add(int u, int v, int w)
    {
        Edge[cnt].v = v;
        Edge[cnt].w = w;
        Edge[cnt].nx = head[u];
        head[u] = cnt++;
    }

    bool bfs()
    {
        l = 1, r = 0;
        for(int i = 1; i <= n; ++i) d[i] = -1;
        q[++r] = S, d[S] = 0, cur[S] = head[S];
        while(l <= r)
        {
            int u = q[l++];
            if(u == T) return 1;
            for(int i = head[u]; ~i; i = Edge[i].nx)
            {
                int v = Edge[i].v;
                if(d[v] == -1 && Edge[i].w)
                {
                    d[v] = d[u] + 1;
                    cur[v] = head[v];
                    q[++r] = v;
                }
            }
        }
        return 0;
    }

    int dfs(int u, int limit)
    {
        if(u == T) return limit;
        int flow = 0;
        for(int i = cur[u]; ~i && flow < limit; i = Edge[i].nx)
        {
            cur[u] = i;
            int v = Edge[i].v;
            if(d[v] == d[u] + 1 && Edge[i].w)
            {
                int t = dfs(v, min(Edge[i].w, limit - flow));
                if(!t) d[v] = -1;
                Edge[i].w -= t, Edge[i^1].w += t, flow += t;
            }
        }
        return flow;
    }

    int Dinic()
    {
        int r = 0, flow;
        while(bfs()) while(flow = dfs(S, inf)) r += flow;
        return r;
    }
}G;

int n, m, S, T;
int a[N + 5], b[N + 5], c[N + 5], d[N + 5];
int s[M + 5];

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    scanf("%d %d %d %d", &n, &m, &S, &T); G.n = n + 1; G.init(); G.S = 0, G.T = n + 1;
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
        s[b[i]] += c[i], s[a[i]] -= c[i];
        G.add(a[i], b[i], d[i] - c[i]), G.add(b[i], a[i], 0);
    }
    int tot = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(s[i] > 0)        G.add(0, i, s[i]), G.add(i, 0, 0), tot += s[i];
        else if(s[i] < 0)   G.add(i, n + 1, -s[i]), G.add(n + 1, i, 0);
    }
    G.add(T, S, inf), G.add(S, T, 0);
    if(G.Dinic() < tot) {printf("No Solution\n"); return 0;}
    int ans = G.Edge[G.cnt - 1].w;
    G.Edge[G.cnt - 1].w = G.Edge[G.cnt - 2].w = 0;
    G.S = S, G.T = T;
    ans += G.Dinic();
    printf("%d\n", ans);
    return 0;
}




The__Flash
5个月前
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int M = (int)2e2;
const int N = (int)20800;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;
const double eps = 1e-9;

struct Graph
{
    int n, m, S, T, cnt;
    int head[M + 5];

    struct node
    {
        int v, w, nx;
    }Edge[N * 2 + 5];

    int d[M + 5];
    int cur[M + 5];
    int q[M + 5], l, r;

    void init()
    {
        cnt = 0;
        for(int i = 0; i <= n; ++i)
        {
            head[i] = -1;
        }
    }

    void add(int u, int v, int w)
    {
        Edge[cnt].v = v;
        Edge[cnt].w = w;
        Edge[cnt].nx = head[u];
        head[u] = cnt++;
    }

    bool bfs()
    {
        l = 1, r = 0;
        for(int i = 1; i <= n; ++i) d[i] = -1;
        q[++r] = S, d[S] = 0, cur[S] = head[S];
        while(l <= r)
        {
            int u = q[l++];
            if(u == T) return 1;
            for(int i = head[u]; ~i; i = Edge[i].nx)
            {
                int v = Edge[i].v;
                if(d[v] == -1 && Edge[i].w)
                {
                    d[v] = d[u] + 1;
                    cur[v] = head[v];
                    q[++r] = v;
                }
            }
        }
        return 0;
    }

    int dfs(int u, int limit)
    {
        if(u == T) return limit;
        int flow = 0;
        for(int i = cur[u]; ~i && flow < limit; i = Edge[i].nx)
        {
            cur[u] = i;
            int v = Edge[i].v;
            if(d[v] == d[u] + 1 && Edge[i].w)
            {
                int t = dfs(v, min(Edge[i].w, limit - flow));
                if(!t) d[v] = -1;
                Edge[i].w -= t, Edge[i^1].w += t, flow += t;
            }
        }
        return flow;
    }

    int Dinic()
    {
        int r = 0, flow;
        while(bfs()) while(flow = dfs(S, inf)) r += flow;
        return r;
    }
}G;

int n, m;
int a[N + 5], b[N + 5], c[N + 5], d[N + 5];
int in[M + 5], out[M + 5];

bool check()
{
    for(int i = 2 * m; i < G.cnt; ++i)
    {
        if(G.Edge[i^1].v == 0)
        {
            if(G.Edge[i].w) return 0;
        }
    }
    return 1;
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    scanf("%d %d", &n, &m); G.n = n + 1; G.init(); G.S = 0, G.T = n + 1;
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
        in[b[i]] += c[i], out[a[i]] += c[i];
        G.add(a[i], b[i], d[i] - c[i]), G.add(b[i], a[i], 0);
    }
    for(int i = 1; i <= n; ++i)
    {
        if(in[i] > out[i])        G.add(0, i, in[i] - out[i]), G.add(i, 0, 0);
        else if(in[i] < out[i])   G.add(i, n + 1, out[i] - in[i]), G.add(n + 1, i, 0);
    }
    G.Dinic();
    if(!check()) {printf("NO\n"); return 0;}
    printf("YES\n");
    for(int i = 0; i < 2 * m; i += 2) printf("%d\n", c[i / 2 + 1] + G.Edge[i^1].w);
    return 0;
}



活动打卡代码 AcWing 2179. 圆桌问题

The__Flash
5个月前
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int M = (int)5e2;
const int N = (int)5e4;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
const double eps = 1e-9;

namespace Graph
{
    int n, m, S, T, cnt;
    int head[M + 5];

    struct node
    {
        int v, w, nx;
    }Edge[N * 2 + 5];

    int d[M + 5];
    int cur[M + 5];
    int q[M + 5], l, r;

    void init()
    {
        cnt = 0;
        for(int i = 0; i <= n; ++i)
        {
            head[i] = -1;
        }
    }

    void add(int u, int v, int w)
    {
        Edge[cnt].v = v;
        Edge[cnt].w = w;
        Edge[cnt].nx = head[u];
        head[u] = cnt++;
    }

    bool bfs()
    {
        l = 1, r = 0;
        for(int i = 1; i <= n; ++i) d[i] = -1;
        q[++r] = S, d[S] = 0, cur[S] = head[S];
        while(l <= r)
        {
            int u = q[l++];
            if(u == T) return 1;
            for(int i = head[u]; ~i; i = Edge[i].nx)
            {
                int v = Edge[i].v;
                if(d[v] == -1 && Edge[i].w)
                {
                    d[v] = d[u] + 1;
                    cur[v] = head[v];
                    q[++r] = v;
                }
            }
        }
        return 0;
    }

    int dfs(int u, int limit)
    {
        if(u == T) return limit;
        int flow = 0;
        for(int i = cur[u]; ~i && flow < limit; i = Edge[i].nx)
        {
            cur[u] = i;
            int v = Edge[i].v;
            if(d[v] == d[u] + 1 && Edge[i].w)
            {
                int t = dfs(v, min(Edge[i].w, limit - flow));
                if(!t) d[v] = -1;
                Edge[i].w -= t, Edge[i^1].w += t, flow += t;
            }
        }
        return flow;
    }

    int Dinic()
    {
        int r = 0, flow;
        while(bfs()) while(flow = dfs(S, inf)) r += flow;
        return r;
    }
};

int m, n;
int r[M + 5];
int c[M + 5];

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    scanf("%d %d", &m, &n);
    for(int i = 1; i <= m; ++i) scanf("%d", &r[i]);
    for(int i = 1; i <= n; ++i) scanf("%d", &c[i]);
    Graph::n = m + n + 1; Graph::init(); Graph::S = 0, Graph::T = m + n + 1;
    for(int i = 1; i <= m; ++i) for(int j = 1; j <= n; ++j) Graph::add(i, m + j, 1), Graph::add(m + j, i, 0);
    for(int i = 1; i <= m; ++i) Graph::add(0, i, r[i]), Graph::add(i, 0, 0);
    for(int i = 1; i <= n; ++i) Graph::add(m + i, m + n + 1, c[i]), Graph::add(m + n + 1, m + i, 0);
    int s = 0; for(int i = 1; i <= m; ++i) s += r[i];
    if(Graph::Dinic() != s) {printf("0\n"); return 0;}
    printf("1\n");
    for(int i = 1; i <= m; ++i)
    {
        for(int j = 2 * (i - 1) * n; j < 2 * i * n; j += 2)
        {
            if(!Graph::Edge[j].w) printf("%d ", Graph::Edge[j].v - m);
        }
        printf("\n");
    }
    return 0;
}




The__Flash
5个月前
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int M = (int)2e2;
const int N = (int)3e4;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
const double eps = 1e-9;

namespace Graph
{
    int n, m, S, T, cnt;
    int head[M + 5];

    struct node
    {
        int v, w, nx;
    }Edge[N * 2 + 5];

    int d[M + 5];
    int cur[M + 5];
    int q[M + 5], l, r;

    void init()
    {
        cnt = 0;
        for(int i = 0; i <= n; ++i)
        {
            head[i] = -1;
        }
    }

    void add(int u, int v, int w)
    {
        Edge[cnt].v = v;
        Edge[cnt].w = w;
        Edge[cnt].nx = head[u];
        head[u] = cnt++;
    }

    bool bfs()
    {
        l = 1, r = 0;
        for(int i = 1; i <= n; ++i) d[i] = -1;
        q[++r] = S, d[S] = 0, cur[S] = head[S];
        while(l <= r)
        {
            int u = q[l++];
            if(u == T) return 1;
            for(int i = head[u]; ~i; i = Edge[i].nx)
            {
                int v = Edge[i].v;
                if(d[v] == -1 && Edge[i].w)
                {
                    d[v] = d[u] + 1;
                    cur[v] = head[v];
                    q[++r] = v;
                }
            }
        }
        return 0;
    }

    int dfs(int u, int limit)
    {
        if(u == T) return limit;
        int flow = 0;
        for(int i = cur[u]; ~i && flow < limit; i = Edge[i].nx)
        {
            cur[u] = i;
            int v = Edge[i].v;
            if(d[v] == d[u] + 1 && Edge[i].w)
            {
                int t = dfs(v, min(Edge[i].w, limit - flow));
                if(!t) d[v] = -1;
                Edge[i].w -= t, Edge[i^1].w += t, flow += t;
            }
        }
        return flow;
    }

    int Dinic()
    {
        int r = 0, flow;
        while(bfs()) while(flow = dfs(S, inf)) r += flow;
        return r;
    }
};

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int n1, n2; scanf("%d %d", &n1, &n2); Graph::n = n2 + 1; Graph::S = 0, Graph::T = n2 + 1; Graph::init();
    for(int i = 1; i <= n1; ++i) Graph::add(0, i, 1), Graph::add(i, 0, 0);
    for(int i = n1 + 1; i <= n2; ++i) Graph::add(i, n2 + 1, 1), Graph::add(n2 + 1, i, 0);
    int u, v; while(~scanf("%d %d", &u, &v) && ~u) Graph::add(u, v, 1), Graph::add(v, u, 0);
    printf("%d\n", Graph::Dinic());
    for(int i = 0; i <= Graph::cnt; i += 2)
    {
        if(Graph::Edge[i].v > n1 && Graph::Edge[i].v <= n2 && !Graph::Edge[i].w)
        {
            printf("%d %d\n", Graph::Edge[i^1].v, Graph::Edge[i].v);
        }
    }
    return 0;
}




The__Flash
5个月前
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int M = (int)1e4;
const int N = (int)1e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
const double eps = 1e-9;

int n, m, S, T, cnt;
int head[M + 5];

struct node
{
    int v, w, nx;
}Edge[N * 2 + 5];

int d[M + 5];
int cur[M + 5];
int q[M + 5], l, r;

void init()
{
    cnt = 0;
    for(int i = 1; i <= n; ++i)
    {
        head[i] = -1;
    }
}

void add(int u, int v, int w)
{
    Edge[cnt].v = v;
    Edge[cnt].w = w;
    Edge[cnt].nx = head[u];
    head[u] = cnt++;
}

bool bfs()
{
    l = 1, r = 0;
    for(int i = 1; i <= n; ++i) d[i] = -1;
    q[++r] = S, d[S] = 0, cur[S] = head[S];
    while(l <= r)
    {
        int u = q[l++];
        if(u == T) return 1;
        for(int i = head[u]; ~i; i = Edge[i].nx)
        {
            int v = Edge[i].v;
            if(d[v] == -1 && Edge[i].w)
            {
                d[v] = d[u] + 1;
                cur[v] = head[v];
                q[++r] = v;
            }
        }
    }
    return 0;
}

int dfs(int u, int limit)
{
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u]; ~i && flow < limit; i = Edge[i].nx)
    {
        cur[u] = i;
        int v = Edge[i].v;
        if(d[v] == d[u] + 1 && Edge[i].w)
        {
            int t = dfs(v, min(Edge[i].w, limit - flow));
            if(!t) d[v] = -1;
            Edge[i].w -= t, Edge[i^1].w += t, flow += t;
        }
    }
    return flow;
}

int Dinic()
{
    int r = 0, flow;
    while(bfs()) while(flow = dfs(S, inf)) r += flow;
    return r;
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    scanf("%d %d %d %d", &n, &m, &S, &T); init();
    for(int i = 1, u, v, w; i <= m; ++i) scanf("%d %d %d", &u, &v, &w), add(u, v, w), add(v, u, 0);
    printf("%d\n", Dinic());
    return 0;
}



活动打卡代码 AcWing 2171. EK求最大流

The__Flash
6个月前
#include <bits/stdc++.h>
using namespace std;

const int M = (int)1e3;
const int N = (int)1e4;
const int inf = 0x3f3f3f3f;

int n, m, S, T, cnt;
int head[M + 5];

struct node
{
    int v, w, nx;
}Edge[N * 2 + 5];

int q[M + 5], l, r;
bool vis[M + 5];
int d[M + 5], pre[M + 5];

void init()
{
    cnt = 0;
    for(int i = 1; i <= n; ++i)
    {
        head[i] = -1;
    }
}

void add(int u, int v, int w)
{
    Edge[cnt].v = v;
    Edge[cnt].w = w;
    Edge[cnt].nx = head[u];
    head[u] = cnt++;
}

bool bfs()
{
    for(int i = 1; i <= n; ++i) vis[i] = 0;
    l = 1, r = 0;
    q[++r] = S, vis[S] = 1, d[S] = inf;
    int u, v;
    while(l <= r)
    {
        u = q[l++];
        if(u == T) return 1;
        for(int i = head[u]; ~i; i = Edge[i].nx)
        {
            v = Edge[i].v;
            if(!vis[v] && Edge[i].w)
            {
                vis[v] = 1;
                d[v] = min(d[u], Edge[i].w);
                pre[v] = i;
                q[++r] = v;

            }
        }
    }
    return 0;
}

int EK()
{
    int s = 0;
    while(bfs())
    {
        s += d[T];
        for(int i = T; i != S; i = Edge[pre[i]^1].v) Edge[pre[i]].w -= d[T], Edge[pre[i]^1].w += d[T];
    }
    return s;
}

int main()
{
    scanf("%d %d %d %d", &n, &m, &S, &T); init();
    for(int i = 1, u, v, w; i <= m; ++i) scanf("%d %d %d", &u, &v, &w), add(u, v, w), add(v, u, 0);
    printf("%d\n", EK());
    return 0;
}



The__Flash
6个月前

输入

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

输出

-1
NO PATH
0
4
3
4
NO PATH
NO PATH
NO PATH



The__Flash
6个月前

数据

5 7
1 5 10000
1 3 1000
1 4 1000
1 2 50
2 4 100
3 5 1000
4 3 500

正确答案

1650

假AC代码输出

2000

之前的假AC代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int M = (int)1e6;
const ll inf = 0x3f3f3f3f3f3f3f3f;

int n, m, cnt;
int head[M + 5];

struct node
{
    int v, w, nx;
}Edge[M + 5];

ll dis[M + 5];
bool vis[M + 5];

void init()
{
    cnt = 0;
    for(int i = 1; i <= n; ++i)
    {
        head[i] = -1;
        dis[i] = inf;
        vis[i] = 0;
    }
}

void add(int u, int v, int w)
{
    Edge[cnt].v = v;
    Edge[cnt].w = w;
    Edge[cnt].nx = head[u];
    head[u] = cnt++;
}

struct cmp
{
    bool operator()(int a, int b)
    {
        return dis[a] > dis[b];
    }
};
priority_queue <int, vector<int>, cmp> q;

void Dijstra(int s)
{
    dis[s] = 0;
    q.push(s);
    while(!q.empty())
    {
        int u = q.top(); q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = head[u]; ~i; i = Edge[i].nx)
        {
            int v = Edge[i].v;
            if(!vis[v] && dis[v] > dis[u] + Edge[i].w)
            {
                dis[v] = dis[u] + Edge[i].w;
                q.push(v);
            }
        }
    }
}

int main()
{
    scanf("%d %d", &n, &m); init();
    for(int i = 1, u, v, w; i <= m; ++i) scanf("%d %d %d", &u, &v, &w), add(u, v, w);
    Dijstra(1);
    printf("%lld\n", dis[n] == inf ? -1 : dis[n]);
    return 0;
}