#include <cstdio>
        #include <cstring>
        #define INF 10000000
        using namespace std;
        int a[1001][1001], d[1001], t[1001];
        bool sel[1001];
        void dijkstra (int n, int p)
        {
            int i, j, k=j, Min; memset(t,0,sizeof(t)); memset(sel,false,sizeof(sel));
            for (i=1; i<=n; i++) d[i]=INF; d[p]=0;
            for (i=1; i<=n; i++)
            {
                Min=INF;
                for (j=1; j<=n; j++)
                {
                    if (Min>d[j] && !sel[j])
                    {
                        Min=d[j]; k=j;
                    }
                }
                sel[k]=true;
                for (j=1; j<=n; j++)
                {
                    if (d[j]>d[k]+a[k][j] && !sel[j])
                    {
                        d[j]=d[k]+a[k][j];
                        t[j]=k;
                    }
                }
            }
        }
        int main()
        {
            int n, m, i, j, x, y, z;
            freopen("dijkstra.in","r",stdin);
            freopen("dijkstra.out","w",stdout);
            scanf("%d%d",&n,&m);
            for (i=1; i<=m; i++)
            {
                for (j=1; j<=n; j++)
                {
                    if (i==j) a[i][j]=0;
                    else a[i][j]=INF;
                }
            }
            for (i=1; i<=m; i++)
            {
                for (j=1; j<=n; j++)
                {
                    scanf("%d%d%d",&x,&y,&z);
                    a[x][y]=z;
                }
            }
            dijkstra(n,1);
            for (i=2; i<=n; i++)
            {
                if (d[i]!=INF) printf("%d ",d[i]);
                else printf("0 ");
            }
            fclose(stdin);
            fclose(stdout);
            return 0;
        }