#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10;
int head[2 * N], dis[N], cnt;
struct edge
{
    int to, w, nt;
} e[2 * N];
void add(int u, int v, int w)
{
    e[cnt].to = v;
    e[cnt].w = w;
    e[cnt].nt = head[u];
    head[u] = cnt++;
}
int n, m;
int sum[N];
bool vis[N];
struct node
{
    int to;
    bool operator<(const node &a) const
    {
        return dis[a.to] < dis[to];
    }
} now, then;
priority_queue<node> q;
void init()
{
    memset(head, -1, sizeof(head));
    memset(dis, 0x7f, sizeof(dis));
    memset(sum, 0, sizeof(sum));
    for (int i = 1; i <= n; i++)
    {
        add(0, i, 0);
    }
    while (!q.empty())
    {
        q.pop();
    }
}
bool spfa()
{
    now.to = 0;
    vis[0] = 1;
    dis[0] = 0;
    q.push(now);
    while (!q.empty())
    {
        now = q.top();
        q.pop();
        vis[now.to] = 0;
        for (int i = head[now.to]; ~i; i = e[i].nt)
        {
            then.to = e[i].to;
            if (dis[then.to] > dis[now.to] + e[i].w)
            {
                dis[then.to] = dis[now.to] + e[i].w;
                sum[then.to] = sum[now.to] + 1;
                if (sum[then.to] >= n)
                {
                    return false;
                }
                if (!vis[then.to])
                {
                    vis[then.to] = 1;
                    q.push(then);
                }
            }
        }
    }
    return true;
}
int main(void)
{
    cin >> n >> m;
    init();
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d %d %d", &v, &u, &w);
        add(u, v, w);
    }
    bool ans = spfa();
    if (ans)
    {
        for (int i = 1; i <= n; i++)
        {
            printf("%d ", dis[i]);
        }
        cout << endl;
    }
    else
        printf("NO\n");
}