# include <cstdio>
# include <vector>
# include <set>

# define mp make_pair
# define pb push_back

using namespace std;

FILE *f = freopen("dijkstra.in", "r", stdin);
FILE *g = freopen("dijkstra.out", "w", stdout);

const int N_MAX = 50000 + 5;
const int M_MAX = 250000 + 5;

vector <pair <int, int> > G[N_MAX];
set <pair<int, int> > s;

int n, m;
int d[N_MAX];

void read()
{
    scanf("%d %d", &n, &m);

    for (int i=1; i<=m; i++)
    {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);

        G[x].pb(mp(y, z));
    }
}

void solve()
{
    s.insert(mp(0, 1));
    d[1] = 0;

    for (int i=2; i<=n; i++)
        d[i] = 1e9;

    while (!s.empty())
    {
        pair <int, int> my_p = *s.begin();
        s.erase(s.begin());

        for (pair <int, int> vecin : G[my_p.second])
        {
            if (d[vecin.first] > d[my_p.second] + vecin.second)
            {
                if (d[vecin.first] != 1e9)
                    s.erase(mp(d[vecin.first], vecin.first));

                d[vecin.first] = d[my_p.second] + vecin.second;
                s.insert(mp(d[vecin.first], vecin.first));
            }
        }
    }
}

void write()
{
    for (int i=2; i<=n; i++)
    {
        if (d[i] != 1e9)
            printf("%d ", d[i]);
        else
            printf("0 ");
    }
}

int main()
{
    read();
    solve();
    write();
    return 0;
}