#include <fstream>
#include <set>
#include <cstring>
#include <vector>
using namespace std;
#define INF 0x3f3f3f
#define pb push_back
#define mkp make_pair
#define ii pair<int,int>
set <ii> Q;
vector < ii > G[250005];
vector <ii> :: iterator it;
int s,m,i,n,D[250005];
int main()
{
    int x,y,c;
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        G[x].pb(mkp(y,c));
    }
    for (i=1;i<=n;i++)
        D[i]=INF;
    D[1]=0;
    Q.insert(mkp(1,0));
    while (!Q.empty())
        {
            ii top = *Q.begin();
            Q.erase(Q.begin());
            int v=top.first;
            for (it=G[v].begin();it!=G[v].end();it++)
                {
                    int v2= it->first;
                    int cost=it->second;
                    if (D[v2]>D[v]+cost)
                        {
                            D[v2] = D[v] + cost;
                            Q.insert (mkp(v2,D[v2]));
                        }
                }
        }
    for (i=2;i<=n;i++)
        if (D[i]==INF) D[i]=0;
    for (i=2;i<=n;i++)
        g<<D[i]<<' ';
}