#include <bits/stdc++.h>
#define intpair pair < int,int >

using namespace std;


ifstream f("dijkstra.in");
ofstream g("dijkstra.out");


const int nmax = 50005;
const int inf = 1 << 30;

int n,m;

vector < pair <int,int> > graf[nmax];
priority_queue < intpair, vector < intpair >, greater < intpair > >  pq;



void addEdge ( int x, int y, int z)
{
    graf[x].push_back(make_pair(y,z));
}


void setup()
{
    f>>n>>m;
    int i, x,y,z;
    for(i= 1 ; i <= m ; i++)
    {
        f>>x>>y>>z;
        addEdge(x,y,z);
    }
}


void dijkstra()
{

    vector < int > d(n + 1,inf);

    pq.push(make_pair(0,1));
    d[1] = 0;

    vector < pair <int, int> > ::iterator it;
    while ( !pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        for( it = graf[u].begin() ; it != graf[u].end(); ++it)
        {
            int v = (*it).first;
            int w = (*it).second;

            if( d[v] > d[u] + w )
            {
                d[v] = d[u] + w;
                pq.push(make_pair(d[v], v));
            }
        }
    }

    for(int i = 2 ; i <= n ; i++)
        {
            if(d[i] == inf)
                g<< 0 << " ";
            else
                g<<d[i]<<" ";
        }
}

int main()
{
    setup();
    dijkstra();
}