#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define inf 0x3f3f3f3f

using namespace std;

vector <pair <int, int> > a[50100];
vector <pair <int, int> >::iterator it;
int d[50010],n,m,x,y,z,i,nod;

struct comp
{
    bool operator () (const int &a, const int &b)
    {
        return (d[a]>d[b]);
    }
};

priority_queue <int, vector<int>, comp > q;




int main()
{
    freopen ("dijkstra.in","r",stdin);
    freopen ("dijkstra.out","w",stdout);

    scanf ("%d %d",&n,&m);

    for (i=1; i<=m; i++)
    {
        scanf ("%d %d %d",&x,&y,&z);
        a[x].pb ( mp(y,z) );
    }

    memset (d, inf, sizeof(d));
    q.push(1);
    d[1] = 0;

    while (!q.empty())
    {
        nod = q.top();
        q.pop();
        for (it = a[nod].begin(); it!=a[nod].end(); it++)
            if ((*it).s + d[nod] < d[(*it).f])
            {
                q.push((*it).f);
                d[(*it).f] = d[nod] + (*it).s;
            }
    }

    for (i=2; i<=n; i++)
        if (d[i] == inf) printf ("0 ");
        else printf ("%d ",d[i]);
    printf ("\n");

    return 0