#include<fstream>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;


const int NMAX = 5e4 + 1;
const int INF = 1e9;

vector<int> dp(NMAX,INF),cate(NMAX);
vector<pair<int,int>> vecini[NMAX];

bitset<NMAX> inq;

class InParser {
    vector<char> str;
    int ptr;
    ifstream fin;

    char getChar() {
        if (ptr == int(str.size())) {
            fin.read(str.data(), str.size());
            ptr = 0;
        }
        return str[ptr++];
    }

    template<class T>
    T getInt() {
        char chr = getChar();
        while (!isdigit(chr) && chr != '-')
            chr = getChar();
        int sgn = +1;
        if (chr == '-') {
            sgn = -1;
            chr = getChar();
        }
        T num = 0;
        while (isdigit(chr)) {
            num = num * 10 + chr - '0';
            chr = getChar();
        }
        return sgn * num;
    }

public:
    InParser(const char* name) : str(1e5), ptr(str.size()), fin(name) { }
    ~InParser() { fin.close(); }

    template<class T>
    friend InParser& operator>>(InParser& in, T& num) {
        num = in.getInt<T>();
        return in;
    }
};

class OutParser {
    vector<char> str;
    int ptr;
    ofstream fout;

    void putChar(char chr) {
        if (ptr == int(str.size())) {
            fout.write(str.data(), str.size());
            ptr = 0;
        }
        str[ptr++] = chr;
    }

    template<class T>
    void putInt(T num) {
        if (num < 0) {
            putChar('-');
            num *= -1;
        }
        if (num > 9)
            putInt(num / 10);
        putChar(num % 10 + '0');
    }

public:
    OutParser(const char* name) : str(1e5), ptr(0), fout(name) { }
    ~OutParser() { fout.write(str.data(), ptr); fout.close(); }

    template<class T>
    friend OutParser& operator<<(OutParser& out, const T num) {
        out.putInt(num);
        return out;
    }

    friend OutParser& operator<<(OutParser& out, const char chr) {
        out.putChar(chr);
        return out;
    }

    friend OutParser& operator<<(OutParser& out, const char* str) {
        for (int i = 0; str[i]; i++)
            out.putChar(str[i]);
        return out;
    }
};


int main()
{
    InParser fin("bellmanford.in");
    OutParser fout("bellmanford.out");

    int n,a,b,c,m; fin >> n >> m;
    for(int i = 1; i <= m ; i++)
        {
            fin >> a >> b >> c;
            vecini[a].push_back({b,c});
        }

    ///Bellman - Ford
    dp[1] = 0;
    queue<int> q; q.push(1);


    inq[1] = 1;

    while(!q.empty())
        {
            int v = q.front(); q.pop();
            inq[v] = 0;

            for(auto it : vecini[v])
                {
                    if((dp[v] + it.second) < dp[it.first])
                        {
                            dp[it.first] = dp[v] + it.second;
                            if(!inq[it.first])
                                {
                                    q.push(it.first);
                                    inq[it.first] = 1;
                                    cate[it.first]++;
                                    if(cate[it.first] > n)
                                        {
                                            fout << "Ciclu negativ!";
                                            return 0;
                                        }
                                }
                        }
                }
        }

    for(int i = 2; i <= n ; i++) fout << dp[i] << " ";

}