#include <fstream>
#include <map>
#include <set>
#include <vector>
#define infinity 1 << 30

using namespace std;

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

vector < map <int,int> > G;
set < pair<int,int> > H;
int n,m,dist[50002];

void Dijkstra()
{
    int i,v;

    for(i=2;i<=n;++i)
    {
        dist[i] = infinity;
        H.insert(make_pair(infinity,i));
    }
    dist[1] = 0;
    H.insert(make_pair(0,1));


    while(!H.empty())
    {
        v = H.begin()->second;
        H.erase(H.begin());

        if(dist[v]==888888) break;

        for(map<int,int>::iterator i = G[v].begin(); i!=G[v].end(); ++i)
        {
            if(dist[v]+i->second < dist[i->first])
            {
                H.erase(H.find(make_pair(dist[i->first],i->first)));
                dist[i->first] = dist[v] + i->second;
                H.insert(make_pair(dist[i->first],i->first));
            }
        }

    }
}

int main()
{
    int a,b,cost;

    f>>n>>m;

    G.resize(n+2);

    while(m--)
    {
        f>>a>>b>>cost;
        G[a][b] = cost;
    }

    Dijkstra();

    for(int i = 2; i <= n; ++i)
    {
        g<<dist[i]<<" ";
    }

    return 0;
}