#include <algorithm>
#include <cstdio>
#include <cstring>
#define N 50002
#define INF 0x3f3f3f3f
using namespace std;

struct graf
{
    int n, cost;
    graf *next;
};

graf *g[N];
int d[N], poz[N], h[N];
int n;

inline void Read()
{
    freopen("dijkstra.in", "r", stdin);
    int m, x, y, cost;
    scanf("%d%d", &n, &m);
    while(m--)
    {
        scanf("%d%d%d", &x, &y, &cost);
        graf *p=new graf;
        p->n=y;
        p->cost=cost;
        p->next=g[x];
        g[x]=p;
    }
}

inline void Write()
{
    freopen("dijkstra.out", "w", stdout);
    for(int i=2;i<=n;i++)
    {
        printf("%d ", d[i]);
    }
}

void upheap(int x)
{
    int f;
    while(x>1)
    {
        f=x/2;
        if(d[f]>d[x])
        {
            poz[h[f]]=x;
            poz[h[x]]=f;
            swap(h[f], h[x]);
        }
        else return;
    }
}

void downheap(int x)
{
    int s;
    while(x<=h[0])
    {
        s=x;
        if(2*x<=h[0])
        {
            s=2*x;
            if(s+1<=h[0]&&d[h[s+1]]<d[h[s]]) s++;
        }
        else return;
        if(d[x]>d[s])
        {
            poz[h[x]]=s;
            poz[h[s]]=x;
            swap(h[x], h[s]);
            x=s;
        }
        else return;
    }
}

inline void dijkstra()
{
    int i, x;
    graf *p;
    memset(d, INF, sizeof(d));
    memset(poz, 0xff, sizeof(poz));
    poz[1]=1;
    d[1]=0;
    h[++h[0]]=1;
    while(h[0])
    {
        x=h[1];
        swap(h[1], h[h[0]]);
        poz[h[1]]=1;
        h[0]--;
        downheap(1);
        for(p=g[x];p;p=p->next)
        {
            if(d[p->n]>d[x]+p->cost)
            {
                d[p->n]=d[x]+p->cost;
                if(poz[p->n]!=-1)
                {
                    upheap(poz[p->n]);
                }
                else
                {
                    h[++h[0]]=p->n;
                    poz[p->n]=h[0];
                    upheap(h[0]);
                }
            }
        }
    }
}

int main()
{
    Read();
    dijkstra();
    Write();
}