#include <iostream>
#include <fstream>
#define NMAX 50001
#include <vector>

using namespace std;

int const INFINIT=1500;
int n,m;
int viz[NMAX],tata[NMAX];
int d[NMAX];
struct cost_nod
{
    int nod,cst;
};
vector<cost_nod> C[NMAX];

int cost(int a, int b)
{
    for(unsigned i=0;i<C[a].size();i++)
        if(C[a][i].nod==b)
            return C[a][i].cst;
    return INFINIT;
}

void dijkstra(int start)
{
    int i,k,ok;
    int min;
    for (i=1;i<=n;i++)
    {
        d[i]=cost(start,i);
        tata[i]=start;
        viz[i]=0;
    }
    tata[start]=0;
    viz[start]=1;
    ok=1;
    while(ok)
    {
        min=INFINIT;
        for(i=1;i<=n;i++)
            if(!viz[i]&&min>d[i])
            {
                min=d[i];
                k=i;
            }
        if(min!=INFINIT)
        {
            viz[k]=1;
            for(i=1;i<=n;i++)
               if(!viz[i]&&d[i]>d[k]+cost(k,i))
               {
                   d[i]=d[k]+cost(k,i);
                   tata[i]=k;
               }
        }
        else ok = 0;
    }
}

int main()
{
    ifstream f1("dijkstra.in");
    f1>>n>>m;
    int a;
    cost_nod x;
    for(int i=0;i<m;i++)
    {
        f1>>a>>x.nod>>x.cst;
        C[a].push_back(x);
    }
    f1.close();
    dijkstra(1);
    ofstream f2("dijkstra.out");
    for(int i=2;i<n;i++)
        if(d[i]==INFINIT)
            f2<<"0 ";
        else
            f2<<d[i]<<" ";
    if(d[n]==INFINIT)
        f2<<"0";
    else
        f2<<d[n];
    f2.close();
    return 0;
}