#include<fstream>
#include<queue>
#define inf 32000
using namespace std;
struct nod{int info,c;nod*adr;}*v[50003],*p;
int n,m,x,y,c,i,dist[50002];
queue<int> Q;
void belman_ford(int nd)
{int j,d;
    Q.push(nd);
    for(i=2;i<=n;i++) dist[i]=inf;
    while(!Q.empty())
    {
        nd=Q.front();
        d=dist[nd];
        p=v[nd];
        while(p)
        {
            j=p->info;
            if(d+p->c < dist[j] )
            {
                dist[j] = d+p->c;
                Q.push(j);
            }
            p=p->adr;
        }
        Q.pop();
    }
}
int main()
{
    ifstream f("dijkstra.in");ofstream g("dijkstra.out");
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        p=new nod;
        p->info=y; p->c=c; p->adr=v[x]; v[x]=p;
    }
    belman_ford(1);

    for(i=2;i<=n;i++)
     if(dist[i]==inf)g<<0<<" ";
        else g<<dist[i]<<" ";
    f.close();g.close();
    return 0;
}