#include <cstdio>
        #include <cstring>
        #include <vector>
        #define INF 10000000
        using namespace std;
        int fiust (int x) {return x*2;}
        int fiudr (int x) {return x*2+1;}
        int tata  (int x) {return x/2;}
        struct dijkstra
        {
            vector <int> nod;
            vector <int> cost;
        };
        dijkstra g[50001];
        int h[50001], dist[50001], poz[50001], t[50001], m;
        void swap (int p, int r)
        {
            int aux=h[p];
            h[p]=h[r];
            h[r]=aux;
            aux=poz[h[p]];
            poz[h[p]]=poz[h[r]];
            poz[h[r]]=aux;
        }
        void heapup (int x)
        {
            if (dist[h[x]]<dist[h[tata(x)]])
            {
                swap(x,tata(x));
                x=tata(x);
                heapup(x);
            }
        }
        void heapdown(int p)
        {
            int st, dr;
            if (fiust(p)>m) return;
            st=h[fiust(p)];
            if (fiudr(p)<=m) dr=h[fiudr(p)];
            else dr=st+1;
            if (st<dr)
            {
                if (dist[h[p]]<st) return;
                swap(p,fiust(p));
                heapdown(fiust(p));
            }
            else
            {
                if (dist[h[p]]<dr) return;
                swap(p,fiudr(p));
                heapdown(fiudr(p));
            }
        }
        int main()
        {
            int n, i, j, x, y, z, Nod;
            freopen("dijkstra.in","r",stdin);
            freopen("dijkstra.out","w",stdout);
            scanf("%d%d",&n,&m);
            for (i=1; i<=n; i++)
            {
                dist[i]=INF;
                h[i]=i;
                poz[i]=i;
            }
            for (i=1; i<=m; i++)
            {
                scanf("%d%d%d",&x,&y,&z);
                g[x].nod.push_back(y);
                g[x].cost.push_back(z);
            } m=n; dist[1]=0;
            for (i=1; i<=n; i++)
            {
                Nod=h[1];
                swap(1,m);
                m--;
                heapdown(1);
                for (j=0; j<g[Nod].nod.size(); j++)
                {
                    if (dist[g[Nod].nod[j]]>dist[Nod]+g[Nod].cost[j])
                    {
                        dist[g[Nod].nod[j]]=dist[Nod]+g[Nod].cost[j];
                        t[g[Nod].nod[j]]=Nod;
                        heapup(poz[g[Nod].nod[j]]);
                    }
                }
            }
            for (i=2; i<=n; i++)
            {
                if (dist[i]!=INF) printf("%d ",dist[i]);
                else printf("0 ");
            }
            fclose(stdin);
            fclose(stdout);
            return 0;
        }