#include <fstream>
#include <vector>
#include <cstring>

#define MAX 50005
#define INF 0x3f3f3f3f
#define PII pair< int , int >
#define f first
#define s second
#define mp make_pair
#define pb push_back

using namespace std;

int n, m, d[MAX], P[MAX], H[MAX], NH, a, b, c;
vector< PII > v[MAX];

inline bool Compare(const int x, const int y)
{
    return d[H[x]] < d[H[y]];
}

inline void Swap(const int x, const int y)
{
    swap(P[H[x]], P[H[y]]);
    swap(H[x], H[y]);
}

void Percolate(const int x)
{
    int dad = x >> 1;
    if(dad && Compare(x, dad))
    {
        Swap(x, dad); Percolate(dad);
    }
}

void Sift(const int x)
{
    int son = x << 1;
    son += (son + 1 <= NH && Compare(son + 1, son));
    if(son <= NH && Compare(son, x))
    {
        Swap(son, x); Sift(son);
    }
}

void Insert(const int x)
{
    H[++NH] = x; P[x] = NH;
    Percolate(P[x]);
}

void Erase(const int x)
{
    Swap(x, NH);
    P[H[NH]] = 0; H[NH--] = 0;
    Sift(x);
}

void Dijkstra()
{
    int nod, dest, cost;
    d[1] = 0;
    Insert(1);
    while(NH)
    {
        nod = H[1];
        for(vector< PII >::iterator it = v[nod].begin(); it != v[nod].end(); it++)
        {
            dest = (*it).f, cost = (*it).s;
            if(d[dest] > d[nod] + cost)
            {
                d[dest] = d[nod] + cost;
                if(P[dest])
                    Percolate(P[dest]);
                else
                    Insert(dest);
            }
        }
        Erase(1);
    }
}

int main()
{
    ifstream in("dijkstra.in"); in>>n>>m;
    for(int i = 1; i <= m; i++)
    {
        in>>a>>b>>c;
        v[a].pb(mp(b, c));
        v[b].pb(mp(a, c));
    } in.close();
    memset(d, INF, sizeof(d));
    Dijkstra();
    ofstream out("dijkstra.out");
    for(int i = 2; i <= n; i++) out<<d[i]<<" ";
    out.close();
    return 0;
}