28pts

#include <cstdio>
#include <cctype>
#include <bitset>
#include <cstring>

using namespace std;

typedef long long ll;
const int N = 5e3 + 10, M = N, inf = 0x3f3f3f3f;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
bitset<N> st;
int q[N], hh, tt = -1, cnt[N];
ll dist[N];

inline void add(register int a, register int b, register int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

inline int spfa()
{
    memset(dist, inf, sizeof dist);
    dist[0] = 0;
    
    q[ ++ tt] = 0;
    st[0] = 1;

    while (tt >= hh)
    {
        register int u = q[hh ++ ];
        st[u] = 0;

        for (register int i = h[u]; ~i; i = ne[i])
        {
            register int j = e[i];
            if (dist[j] > dist[u] + (ll)w[i])
            {
                dist[j] = dist[u] + (ll)w[i];

                if (!st[j])
                {
                    q[ ++ tt] = j;
                    st[j] = 1, cnt[j] ++ ;

                    if (cnt[j] >= n + 1)
                        return 1;
                }
            }
        }
    }

    return 0;
}

template<typename T> inline void read(register T &qwq)
{
    register T x = 0, f = 1;
    register char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    qwq = x * f;
    return;
}

template<typename T> inline void write(register T x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
    return;
}

int main()
{
    read(n), read(m);

    memset(h, -1, sizeof h);
    for (register int i = 1; i <= n; i ++ )
        add(0, i, 0);
    
    for (register int i = 1, a, b, c; i <= m; i ++ )
    {
        read(b), read(a), read(c);
        add(a, b, c);
    }

    if (spfa())
        puts("NO");
    else for (register int i = 1; i <= n; i ++ )
        write(dist[i]), putchar(' ');

    return 0;
}

82pts

#include <cstdio>
#include <cctype>
#include <bitset>
#include <cstring>

using namespace std;

typedef long long ll;
const int N = 5e4 + 10, M = N, inf = 0x3f3f3f3f;//这里改成5e5 + 10仍为82pts

int n, m;
int h[N], e[M], w[M], ne[M], idx;
bitset<N> st;
int q[N], hh, tt = -1, cnt[N];
ll dist[N];

inline void add(register int a, register int b, register int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

inline int spfa()
{
    memset(dist, inf, sizeof dist);
    dist[0] = 0;
    
    q[ ++ tt] = 0;
    st[0] = 1;

    while (tt >= hh)
    {
        register int u = q[hh ++ ];
        st[u] = 0;

        for (register int i = h[u]; ~i; i = ne[i])
        {
            register int j = e[i];
            if (dist[j] > dist[u] + (ll)w[i])
            {
                dist[j] = dist[u] + (ll)w[i];

                if (!st[j])
                {
                    q[ ++ tt] = j;
                    st[j] = 1, cnt[j] ++ ;

                    if (cnt[j] >= n + 1)
                        return 1;
                }
            }
        }
    }

    return 0;
}

template<typename T> inline void read(register T &qwq)
{
    register T x = 0, f = 1;
    register char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    qwq = x * f;
    return;
}

template<typename T> inline void write(register T x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
    return;
}

int main()
{
    read(n), read(m);

    memset(h, -1, sizeof h);
    for (register int i = 1; i <= n; i ++ )
        add(0, i, 0);
    
    for (register int i = 1, a, b, c; i <= m; i ++ )
    {
        read(b), read(a), read(c);
        add(a, b, c);
    }

    if (spfa())
        puts("NO");
    else for (register int i = 1; i <= n; i ++ )
        write(dist[i]), putchar(' ');

    return 0;
}

100pts

#include <cstdio>
#include <cctype>
#include <bitset>
#include <cstring>

using namespace std;

typedef long long ll;
const int N = 5e6 + 10, M = N, inf = 0x3f3f3f3f;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
bitset<N> st;
int q[N], hh, tt = -1, cnt[N];
ll dist[N];

inline void add(register int a, register int b, register int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

inline int spfa()
{
    memset(dist, inf, sizeof dist);
    dist[0] = 0;
    
    q[ ++ tt] = 0;
    st[0] = 1;

    while (tt >= hh)
    {
        register int u = q[hh ++ ];
        st[u] = 0;

        for (register int i = h[u]; ~i; i = ne[i])
        {
            register int j = e[i];
            if (dist[j] > dist[u] + (ll)w[i])
            {
                dist[j] = dist[u] + (ll)w[i];

                if (!st[j])
                {
                    q[ ++ tt] = j;
                    st[j] = 1, cnt[j] ++ ;

                    if (cnt[j] >= n + 1)
                        return 1;
                }
            }
        }
    }

    return 0;
}

template<typename T> inline void read(register T &qwq)
{
    register T x = 0, f = 1;
    register char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    qwq = x * f;
    return;
}

template<typename T> inline void write(register T x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
    return;
}

int main()
{
    read(n), read(m);

    memset(h, -1, sizeof h);
    for (register int i = 1; i <= n; i ++ )
        add(0, i, 0);
    
    for (register int i = 1, a, b, c; i <= m; i ++ )
    {
        read(b), read(a), read(c);
        add(a, b, c);
    }

    if (spfa())
        puts("NO");
    else for (register int i = 1; i <= n; i ++ )
        write(dist[i]), putchar(' ');

    return 0;
}