#include<cstdio>
using namespace std;
#define inf 1<<30
struct muchie {int x,y,c;} G[250005];
int n,m,x,y,c,D[50005];
bool ok;
void citire()
{
    int i;
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;++i)
        {
            scanf("%d%d%d",&x,&y,&c);
            G[i].x=x, G[i].y=y, G[i].c=c;
            if (x==1) D[y]=c;
        }
    for (i=2;i<=n;++i)
        if (!D[i]) D[i]=inf;
}
int main()
{
    int i;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    while (!ok)
        {
            ok=true;
            for (i=1;i<=m;++i)
                {
                    x=G[i].x, y=G[i].y;
                    if (D[y]>D[x]+G[i].c)
                        {
                            D[y]=D[x]+G[i].c;
                            ok=false;
                        }
                }
        }
    for (i=2;i<=n;++i)
        if (D[i]!=inf) printf("%d ",D[i]);
        else printf("0 ");
    printf("\n");
    return 0;
}