#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f("bellmanford.in");

ofstream g("bellmanford.out");

#define pb push_back

#define mp make_pair

#define nod first

#define cost second
#define inf 1e9

vector <pair<int,int>> G[250005];

vector <pair<int,int>> :: iterator vecin;

queue <int> Q;

bool used[50005];

int n,m,x,c,y,D[50005],itnod[50005];
int main()
{
    f>>n>>m;

    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>c;

        G[x].pb(mp(y,c));
    }

    for(int i=1;i<=n;i++)
    {
        D[i]=inf;

        used[i]=false;

        itnod[i]=0;


    }

     D[1]=0;

     Q.push(1);

        while(!Q.empty())
        {
            int Nod=Q.front();

            Q.pop();

            used[Nod]=false;

            for(vecin=G[Nod].begin(); vecin!=G[Nod].end();++vecin)
            {
                if(D[(*vecin).nod]>D[Nod]+(*vecin).cost)
                {
                    D[(*vecin).nod]=D[Nod]+(*vecin).cost;

                    if(!used[(*vecin).nod])
                    {
                        used[(*vecin).nod]=true;

                        Q.push((*vecin).nod);

                        if(++itnod[(*vecin).nod]>n)
                        {
                            g<<"Ciclu negativ"<<'\n';

                        }

                    }
                }
            }
        }


for(int i=2;i<=n;i++)
    g<<D[i]<<" ";

    return 0;
}