#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int nmax = 50000;
const int inf = 0x3f3f3f3f;

class GRAPH
{
private:
    int n;
    vector <pair<int, int> > graph[nmax+5];
    int viz[nmax+5];
    bool in_queue[nmax+5];
public:
    GRAPH(int N) {n=N;memset(viz, 0, sizeof(viz));memset(in_queue, 0, sizeof(in_queue));}
    void push(int x, int y, int cost)
    {
        graph[x].push_back(pair <int, int> (y, cost));
    }
    void Dijkstra(int nod, vector <int> &dist)
    {
        fill(dist.begin(), dist.end(), inf);
        queue <int> q;
        while(!q.empty())q.pop();
        dist[nod] = 0;
        q.push(nod);
        in_queue[nod] = true;
        while(!q.empty())
        {
            int nod = q.front();
            q.pop();
            in_queue[nod] = false;
            for(int i=0; i<graph[nod].size(); i++)
            {
                pair <int, int> New = graph[nod][i];
                if(dist[nod] + New.second < dist[New.first])
                {
                    dist[New.first] = dist[nod] + New.second;
                    if(!in_queue[New.first])
					{
						if(viz[New.first] > n)
						{
							printf("Ciclu negativ!\n");
							return;
						}
						else
						{
							in_queue[New.first] = true;
							q.push(New.first);
							viz[New.first]++;
						}
					}
                }
            }
        }
        for(int i=2; i<dist.size(); i++)
            printf("%d ", dist[i]);
        printf("\n");
    }
};

int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    int n, m;
    scanf("%d%d", &n, &m);
    vector <int> dst;
    dst.resize(n+1);
    GRAPH G(n);
    for(int i=0; i<m; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        G.push(a, b, c);
    }
    G.Dijkstra(1, dst);
    return 0;
}