#include <fstream>
#include <utility>
#include <vector>
#define NMAX 50005
#define INF 999999999

using namespace std;

FILE* f=freopen("dijkstra.in","r",stdin);
FILE* o=freopen("dijkstra.out","w",stdout);

int n,m;
vector<pair<int, int> > graph[NMAX];
int heap[NMAX];
int ph[NMAX];
int dist[NMAX];
int l;

void Swap(int a, int b)
{
    swap(ph[heap[a]],ph[heap[b]]);
    swap(heap[a],heap[b]);
}

void Shift(int p)
{
    int c=p*2;
    while(c<=l)
    {
        if(c<l&&dist[heap[c]]>dist[heap[c+1]]) c+=1;
        if(dist[heap[p]]>dist[heap[c]]) {
            Swap(p,c);
            p=c;
            c=p*2;
        }
        else break;
    }
}

void Push(int c)
{
    int p=c/2;
    while(p>=1)
    {
        if(dist[heap[p]]>dist[heap[c]])
        {
            Swap(p,c);
            c=p;
            p=c/2;
        }
        else break;
    }
}

int Pop()
{
    int r=heap[1];
    Swap(1,l);
    ph[heap[l]]=-1;
    l-=1;
    Shift(1);
    return r;
}

void Dijkstra(int start)
{
    for(int i=1;i<=n;++i)
    {
        dist[i]=INF;
        heap[i]=i;
        ph[i]=i;
    }

    Swap(1,start);
    dist[1]=0;
    l=n;

    while(l)
    {
        int nod=Pop();
        for(int i=0;i<graph[nod].size();++i)
        {
            int ind=graph[nod][i].first;
            int cost=graph[nod][i].second;
            if(ph[ind]!=-1&&dist[nod]+cost<dist[ind])
            {
                dist[ind]=dist[nod]+cost;
                Push(ph[ind]);
            }
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);

    for(int i=0;i<m;++i)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        graph[x].push_back(make_pair(y,c));
    }

    Dijkstra(1);

    for(int i=2;i<=n;++i)
    {
        printf("%d ",dist[i]);
    }

    return 0;
}